问如何在dijkstra算法中保存最短路径

EN

s -> u -> v
where u = prev[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

// 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;
}

# define INF 0x3f3f3f3f
// iPair ==> Integer Pair
typedef pair<int, int> iPair;

void addEdge(vector <pair<int, int> > adj[], int u, int v, int wt)
{
    adj[u].push_back(make_pair(v, wt)); 
    adj[v].push_back(make_pair(u, wt));
}
void shortestPath(vector<pair<int, int> > adj[], int V, int src, int target)
{
    priority_queue< iPair, vector <iPair>, greater<iPair> > pq;
    vector<int> dist(V, INF);
    vector<bool> visited(V, false);
    vector<int> prev(V, -1);
    pq.push(make_pair(0, src));
    dist[src] = 0;
    while (!pq.empty() && !visited[target])
    {
        int u = pq.top().second; 
        pq.pop();
        if (visited[u]) {
            continue;
        }
        visited[u] = true;
        for (auto x : adj[u])
        {
            int v = x.first;
            int weight = x.second;

            if (dist[v] > dist[u] + weight)
            {
                //relax
                dist[v] = dist[u] + weight;
                pq.push(make_pair(dist[v], v));
                prev[v] = u;
            }
        }
    }

    vector<int> res;
    res.push_back(target);
    int temp = target;
    while (temp != 0)
    {
        temp = prev[temp];
        res.push_back(temp);
    }
    //cout << res;
}
int main()
{
    const int V = 9;
    vector<iPair > adj[V];
    addEdge(adj, 0, 1, 4);
    addEdge(adj, 0, 7, 8);
    addEdge(adj, 1, 2, 8);
    addEdge(adj, 1, 7, 11);
    addEdge(adj, 2, 3, 7);
    addEdge(adj, 2, 8, 2);
    addEdge(adj, 2, 5, 4);
    addEdge(adj, 3, 4, 9);
    addEdge(adj, 3, 5, 14);
    addEdge(adj, 4, 5, 10);
    addEdge(adj, 5, 6, 2);
    addEdge(adj, 6, 7, 1);
    addEdge(adj, 6, 8, 6);
    addEdge(adj, 7, 8, 7);

    shortestPath(adj, V, 0, 6);     //the last one means target
    return 0;
}