CODEWITHSUNDEEP
c++algorithmgraphdijkstra
kshitij singh
kshitij singh

Reputation: 363

dijkstra implememtation giving wrong outputs

i am trying to solve a problem for my understanding of dijkstra algorithm .this is the mentioned problem : https://www.hackerrank.com/challenges/dijkstrashortreach . only the first testcase is accepted all others are wrong.please anyone hint me what could be wrong with my implementation . as far as i understand the algorithm i have implemented it correctly

Here is my code:

#include<bits/stdc++.h>
using namespace std;
#define MAX 100001
#define INF INT_MAX
#define pii pair< int, int >
#define pb(x) push_back(x)

int main() {
int i, u, v, w, sz, nodes, edges, starting;
int t;
cin>>t;
while(t--){
    priority_queue< pii, vector< pii >, greater< pii >  > Q;
    vector< pii > G[MAX];
    int D[MAX];
    bool F[MAX];
    // create graph
    scanf("%d %d", &nodes, &edges);
    for(i=0; i<edges; i++) {
        scanf("%d %d %d", &u, &v, &w);
        G[u].pb(pii(v, w));
        G[v].pb(pii(u, w)); // for undirected
    }
    scanf("%d", &starting);
    // initialize distance vector
    for(i=1; i<=nodes; i++) { D[i] = INF; F[u] = 0;}
    D[starting] = 0;
    Q.push(pii(starting, 0));
    // dijkstra
    while(!Q.empty()) {
        u = Q.top().first;
        Q.pop();
        if(F[u]) continue;
        sz = G[u].size();
        for(i=0; i<sz; i++) {
            v = G[u][i].first;
            w = G[u][i].second;
            if(!F[v] && D[u]+w < D[v]) {
                    D[v] = D[u] + w;
                    Q.push(pii(v, D[v]));
            }
        }
        F[u] = 1; // done with u
    }
// result
    for(i=1; i<=nodes; i++){
        if(i!=starting){
        if(D[i]==INF)printf("%d ",-1);
        printf("%d ",D[i]);
    }
  }
}
return 0;
}

Upvotes: 0

Views: 100

Answers (1)

Pham Trung
Pham Trung

Reputation: 11284

Your min heap is not correct, you need to define comparison function for your pair. Using greater is not enough.

This is the comparison C++ using for pair, 

template <class T1, class T2>
  bool operator<  (const pair<T1,T2>& lhs, const pair<T1,T2>& rhs)
{ return lhs.first<rhs.first || (!(rhs.first<lhs.first) && lhs.second<rhs.second); }

You can see that, it always compares first then second, but your ideal behavior should be compared second before first (as in your case, first is the node id, and second is its weight). For more details, please look here

Or, you can just reverse position of first and second in your pair.

One more problem is 

for(i=1; i<=nodes; i++) { D[i] = INF; F[u] = 0;}

Should be:

for(i=1; i<=nodes; i++) { D[i] = INF; F[i] = 0;}

Last problem is, for each new test case, you need to print the result in a new line, plus, your last if condition is not correct. It should be:

for(i=1; i<=nodes; i++){
    if(i!=starting){
        if(D[i]==INF)
            cout << -1 << " ";
        else    
            cout << D[i] << " ";
    }
}
cout << endl;

My code has been accepted after all those changes.

Upvotes: 1

Related Questions