0
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • $\begingroup$ Find the shortest, then delete the path and run the algorithm on the smaller graph. $\endgroup$ – David G. Stork Aug 29 at 19:15
  • 2
    $\begingroup$ @DavidG.Stork what do you mean by deleting the path? What if the second shortest path could contain an edge existing in that path? For instance, say the shortest path from node 1 to node 4 is (1-2-3-4). If there is another path as (1-2-5-4), and if I delete the first path, then how can the algorithm identify the second shortest path? $\endgroup$ – whitepanda Aug 29 at 19:19
  • $\begingroup$ See here: stackoverflow.com/questions/4971850/… $\endgroup$ – Math1000 Aug 29 at 19:36
  • $\begingroup$ @Math1000 That answer is given for the weighted graphs. I believe there should be something faster in my case that will return the solution in seconds( hopefully). Please consider that I might have thousands of nodes. So I need the most efficient way to do this. $\endgroup$ – whitepanda Aug 29 at 19:44
  • $\begingroup$ @whitepanda: I'm not sure this is optimal, but I would delete the first segment of the shortest path and then run the algorithm. Then I would replace that segment and delete the second segment, and then run the algorithm. Then replace that segment and delete the third, ... and so forth. This forces the second shortest to differ by at least one segment from the global shortest path. $\endgroup$ – David G. Stork Aug 29 at 20:25
1
$\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$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ When I conduct this operation from every node to every other node in a large, dense graph, does it run efficiently? $\endgroup$ – whitepanda Aug 29 at 19:42
  • $\begingroup$ It will run in polynomial time: $n^2$ paths $P$ each w at most $n$ edges so $n^3$ BFSs. There may be a faster way to do it than this though. $\endgroup$ – Mike Aug 29 at 19:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.