Modifying Dijkstra's algorithm to print the nodes in the shortest path

I'm wondering how I can modify this function to save the final shortest path of nodes. This is from my textbook with minor modificatons.

template <class vType, int size>
void weightedGraphType<vType, size>::shortestPath(vType vertex) {
int i, j;
double minWeight;

for (j = 0; j < gSize; j++) {
    smalles开发者_运维问答tWeight[j] = weights[vertex][j];
}

bool weightFound[size];

for (j = 0; j < gSize; j++) {
    weightFound[j] = false;
}

for (i = 0; i < gSize; i++) {
    int v;
    cout << vertex << " to " << i << endl;
    minWeight = INFINITY;

    for (j = 0; j < gSize; j++) {
        if (!weightFound[j]) {
            if (smallestWeight[j] < minWeight) {
                v = j;
                minWeight = smallestWeight[v];
            }
        }
    }

    weightFound[v] = true;

    for (j = 0; j < gSize; j++) {
        if (!weightFound[j]) {
            if (minWeight + weights[v][j] < smallestWeight[j]) {
                smallestWeight[j] = minWeight + weights[v][j];
            }
        }
    }
} //end for
} //end shortestPath

Here's a hint: for each node, you know the smallest weight you have found to reach it. You also could know where that "shortest path to reach this node" came from right before you hit this node.

Create array to remember the predecessor of destination node and then track back.

Here is the full implementation of modified dijkstra

#include<stdlib.h>
#include<set>
#include<iostream>
#include<vector>
#include<list>
#include<limits.h>
using namespace std;
    struct myHeapcmp{
     bool operator()(const pair<int,int> &a,const pair<int,int>&b){
      return a.second<b.second;
     }

    };

typedef list<pair<int,int> > AdjList;
typedef vector<AdjList> Graph;
typedef multiset<pair<int,int>,myHeapcmp>MinHeap;
vector<int> dijkstra(Graph g,int N,int s){
    vector<int>d(N,100);
    vector<int>  predecessor(N);
    d[s] =0;
    vector<int>p(N,-1);
    vector<MinHeap::iterator>HeapPos(N);
    MinHeap h;
    for(int i=0;i<N;i++)
     HeapPos[i] = h.insert(make_pair(i,d[i]));
     MinHeap::iterator it;
    while(h.size()>0){
     it = h.begin();
     int v = it->first;

     h.erase(it);
     AdjList::iterator it2;
     for(it2=g[v].begin();it2!=g[v].end();it2++){
       int u = it2->first;
       int w_uv= it2->second;
       if(d[u]>w_uv+d[v]){
         d[u]= w_uv+d[v];
         predecessor[u] = v;
         p[u]=v; h.erase(HeapPos[u]);
         HeapPos[u]= h.insert(make_pair(u,d[u]));
       }

     }
    }
    for(int i = 0;i<N;i++){
        int node = i;
        int pre = predecessor[i];
        cout<<i<<" :";
        while(pre!=s){
            cout<<pre<<" ";
            node = pre;
            pre = predecessor[node];
        }
        cout<<s<<endl;
    }

 return d;
}

one way to do this would be to introduce one extra loop that iterates the algorithm over all the nodes, and with distance array you can store the "via node" element. once you have shortest path calculated from each node to every other node, all you have to do is to follow the "via node" value that you have stored. btw, in terms of efficiency, this algorithm sucks, it's O(n^3).