How to save the shortest path in dijkstra algorithm

Question

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

Answer 1

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

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

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

There can be several nodes in the path from s to u between them, so to restore the path from s to v , you simply return along the path defined by the prev[] array using the code fragment below the main pseudocode ( target 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 

Answer 2

Most libraries that use this algorithm are more likely to give you a way to do this. But in general, just track the path to each node. Those. give each node attrribute shortestPathToNode in which you store the list of nodes

Answer 3

One very short way to do this is to use recursion and the "parent array". If you initialize all the parents of the points to -1, and then when you finish dijkstra, update the parent array, you can go back from any point until you reach the source and print the path. Here is a very short and understandable fragment of recursion:

 // Function to print shortest path from source to j using parent array void path(parent array, int j) {    // Base Case : If j is source    if (jth element of parent is -1) return;    path(parent, jth element of parent); print j; } 

Note that instead of typing "j", you can save it in a global vector (or other data type for languages ​​that are not related to C) for later use.