CODEWITHSUNDEEP
c++graph
s00pcan
s00pcan

Reputation: 163

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++) {
    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

Upvotes: 4

Views: 5924

Answers (3)

user2258408
user2258408

Reputation: 63

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

Upvotes: 0

user959135
user959135

Reputation: 31

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).

Upvotes: -2

dfan
dfan

Reputation: 5824

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.

Upvotes: 4

Related Questions