Can I use Dijkstra's Algorith for finding ALL shortest paths?

Question

Suppose I know by promise that there are lots of paths from $v_s$ to $v_e$ in some graph $G \ni v_i$. Is there a way to modify Dijkstra's algorithm to find all shortest paths rather than just one (which is based on the way I visit nodes)?

Answer 1

Dykstra's algorithm gives you all the shortest paths from your beginning node $v_s$ to every other node in the graph. If throughout the course of the algorithm you keep track of all these paths in addition to just their weights, you'll get what you want.

Answer 2

At completion, Dijkstra's algorithm will have computed the length of the shortest path from your starting node to every other node in the graph (or at least, every other node that could possibly be on a shortest path--I think it's possible to terminate the algorithm without fully exploring parts of the graph that are clearly not going to be used by the shortest path).

In particular, your end node $v_e$ is now marked with the length of the shortest path to it, and each node connected to it is marked with the cost of the shortest path to that node. Let $\mathrm{cost}(u,v)$ denote the length of the link from node $u$ to node $v,$ and $\mathrm{cost}(v)$ denote the length of the shortest path found from $v_s$ to $v.$ If $v$ is a neighbor of $v_e$ and $v$ is on the shortest path from $v_s$ to $v_e,$ then $$\mathrm{cost}(v_e) = \mathrm{cost}(v) + \mathrm{cost}(v,v_e).$$ But any neighbor $v$ of $v_e$ that satisfies this equation is also on a "shortest path". Similarly, if $v$ is on a "shortest path" and $u$ is a neighbor of $v$ such that $\mathrm{cost}(v) = \mathrm{cost}(u) + \mathrm{cost}(u,v),$ then $u$ is also on a shortest path whose next node is at $v.$

You can perform a depth-first search (starting at $v_e$) that will find each of these paths one at a time. When you visit a node $v$ for the first time, continue to a neighbor of $v$ that precedes $v$ on a shortest path. Each time you find a path, backtrack to the nearest node where there is still a neighbor that is on a shortest path and has not yet been visited.

Answer 3

Consider this algorithm: https://www.programmingalgorithms.com/algorithm/dijkstra's-algorithm/php/ At the end there is a "< \$distance[$v])" condition. If we change it to "<= ...", it will give all the existing shortest paths.

For collecting the paths we can put a

\$this->paths[\$v][] = \$u; row here also. The whole code is here: https://pastebin.com/gk2ymyWw