how to save shortest path in dijkstra algorithm

Daniel.V picture Daniel.V · Mar 11, 2015 · Viewed 12.9k times · Source

So first let's define Dijkstra algorithm:
Dijkstra's algorithm finds single-source shortest paths in a directed graph with non-negative edge weights.
I want to know how can I save the shortest path form s to t with Dijkstra algorithm.
I searched on google, but I couldn't find anything particular; I also changed Dijkstra algorithm, but I could't get any answer. How can I save the shortest path from s to t with Dijkstra?
I know my question is basic and unprofessional, but any help would be appreciated. Thanks for considering my question.

Answer

beaker picture beaker · Mar 12, 2015

If you look at the pseudocode from the Wikipedia link you gave, you'll see an array in there called prev[]. This array contains, for each node v in the graph, the previous node u in the shortest path between the source node s and v. (This array is also called the predecessor or parent array.)

In other words, the shortest path between s and v is:

s -> u -> v
where u = prev[v]

The path from s to u might have several nodes in between, so to reconstruct the path from s to v, you just walk back along the path defined by the prev[] array using the code snippet below the main pseudocode (target is v):

1  S ← empty sequence
2  u ← target
3  while prev[u] is defined:                 // Construct the shortest path with a stack S
4      insert u at the beginning of S          // Push the vertex onto the stack
5      u ← prev[u]                             // Traverse from target to source
6  end while