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.
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