how to save shortest path in dijkstra algorithm

问题:

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.

回答1:

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

回答2:

Most libraries that use this algorithm will likely give you a way to do this. But in general just keep track of the path to each node. Ie give each node an attrribute shortestPathToNode in which you store the list of nodes

回答3:

One extremely short way to do so is to use recursion and a "parent array." If you initialize all of the points' parents to -1, and then as you complete dijkstra's, update the parent array, you are able to recurse back from any point till you get to the source and print out the path. Here is a very short and easy to understand recursion snippet:

// 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 printing "j" out, you can store it in a global vector (or other datatype for languages that are not C-related) for later use.