I have tried to find and print more than one successive shortest paths between two vertices in the undirected graph. Using BFS as DFS will not be optimal in this case, as it can go deep into the stack.

Wrote this function but not getting the correct response and also tried to find help over StackOverflow and other platforms but did not find a solution for undirected graph.

  • $\begingroup$ Is the graph weighted? $\endgroup$ – Steven Apr 13 at 20:46
  • 1
    $\begingroup$ en.wikipedia.org/wiki/K_shortest_path_routing $\endgroup$ – D.W. Apr 13 at 21:07
  • $\begingroup$ Coding questions are off-topic here. Not everyone here knows C++. Please edit the question to replace the code with concise pseudocode. $\endgroup$ – D.W. Apr 13 at 21:08
  • $\begingroup$ @D.W. It'm not sure that the question is about finding $k$ successive shortest paths in a graph (which might have different lengths). It seems to me that the goal is to find $k$ distinct paths from $s$ to $t$, all of which are shortest. It might be worth to clarify this in the question. Clearly a solution for the first problem implies a solution for the second problem (but not vice-versa). $\endgroup$ – Steven Apr 13 at 21:17
  • $\begingroup$ @Steven, hmm, if it's unclear, perhaps this should be put on hold until that is cleared up. Is there a difference? If there are $k$ distinct paths all tied for shortest, then using an algorithm for finding the $k$ shortest paths will find all of them. If there aren't, that will also be apparent after running an algorithm to find the $k$ shortest paths. $\endgroup$ – D.W. Apr 13 at 21:20

Your Answer

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

Browse other questions tagged or ask your own question.