Given an unweighted and undirected graph, can I identify the second best shortest path from every node to every other node in polynomial time? When I say the second best, as long as one edge is different than the edges existing in the first shortest path, it is acceptable. This also implies that the length of the paths can be equal.
If so, what is the algorithm that I should use?
$\endgroup$ 51 Answer
$\begingroup$A naive way that would work is the following: Let $P$ be a shortest path from $u$ to $v$. For each $e \in P$ find the shortest path $P_{e}$ in $G \setminus \{e\}$. Then the shortest of the $P_{e}$s, $e \in P$, is a second shortest path from $u$ to $v$.
$\endgroup$ 3
