On the second point‐to‐point undirected shortest simple path problem

We address the determination of the second point‐to‐point shortest simple path in undirected networks. The effective reduced cost concept is introduced to compute the second best solution. This concept is used to prove that a path tree containing the second point‐to‐point shortest simple path is adjacent to any shortest path tree. Therefore, this result immediately implies a method requiring O(m) time once that the shortest path tree is obtained on an undirected network with n nodes and m edges.