Changing Dijkstra's algorithm for printing nodes in the shortest way

Question

I am wondering how I can change this function to save the final shortest path of nodes. This is from my tutorial with minor modifications.

template <class vType, int size> void weightedGraphType<vType, size>::shortestPath(vType vertex) { int i, j; double minWeight; for (j = 0; j < gSize; j++) { smallestWeight[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 

Answer 1

Here's a tip: for each node, you know the least weight you found to achieve it. You can also find out where this “shortest path to reach this node” appeared right before you click this node.

Answer 2

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

Here is the full implementation of the 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; } 

Answer 3

one way to do this would be to introduce one additional loop that repeats the algorithm across all nodes, and with the help of an array of distances you can save the element "through node". as soon as you have the shortest path calculated from each node to all other nodes, all you have to do is follow the value you saved "through node". btw, in terms of efficiency, this algorithm sucks, it is O (n ^ 3).