Is there any bug in this dijkstra algorithm implementation?

Question

I just learnt Dijkstra's algorithm and solved a few problems and I am trying to solve this http://codeforces.com/problemset/problem/20/C problem but I am getting Wrong Answer in test case 31.I could not understand why it's getting wrong answer. First it was giving memory limit exceeded on test case 31. But when i change int to long long of d[] arrray it's getting wrong answer. Please Let me know why it's getting wrong answer.

My code:

#include <bits/stdc++.h>

using namespace std;

typedef struct data Data;

struct data{
    long long int city,dis;
    bool operator < (const data & p) const{
        return dis > p.dis;
    }
};

#define tr(niloy,it) for(auto it = niloy.rbegin(); it != niloy.rend(); it++)

void dijkstra(const vector <long long int>  edge[],const vector <long long int>  cost[], int source, int destination,int n,int m)
{
    long long int d[n];
    bool nodes[n];
    vector <int> parent(n,-1);
    for(int i = 0; i < n; i++){
        d[i] = INT_MAX;
        parent[i] = -1;
        nodes[i] = false;
    }
    priority_queue <Data> p;
    Data u,v;
    u.city = 0;
    u.dis = 0;
    p.push(u);
    d[source] = 0;
    while(!p.empty()){
        u = p.top();
        p.pop();
        long long int ucost = d[u.city];
        if(u.city == destination)break;
        if(nodes[u.city])continue;
        nodes[u.city] = true;
        //cout << edge[u.city].size() << endl;
        for(int i = 0; i < edge[u.city].size(); i++){
            v.dis = ucost + cost[u.city][i];
            v.city = edge[u.city][i];
            if(d[v.city] > v.dis){
                ///cout << v.city << " " << u.city << endl;
                parent[v.city] = u.city;
                d[v.city] = v.dis;
                p.push(v);
            }
        }
    }
    vector<int> niloy;
    ///cout << d[destination] << endl;
    if(parent[destination] != -1){
        niloy.push_back(n);
        while(destination != 0){
            niloy.push_back(parent[destination]+1);
            destination = parent[destination];
        }
        tr(niloy,it)cout << *it << " " ;
    }else{
        ///cout << d[destination] << endl;
        cout << -1 << endl;
    }

}

int main()
{
    int n,m;
    cin>> n >> m;
    vector <long long int> edge[n],cost[n];

    int a,b,c;

    for(int i = 0; i < m; i++){
        cin >> a >> b >> c;
        if(a == b)continue;
        edge[a-1].push_back(b-1);
        cost[a-1].push_back(c);
        edge[b-1].push_back(a-1);
        cost[b-1].push_back(c);
    }
    //cout << edge[0][0] << endl;
    dijkstra(edge,cost,0,n-1,n,m);

    return 0;
}

"Is there a bug in this implementation" + "I am getting Wrong Answer" = yes, you have a bug. Does this website provide the test case that failed? — JohnFilleau, Mar 22 '20 at 20:25
Unrelated to your problem, but please read [Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) as well as [Why is “using namespace std;” considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) — Some programmer dude, Mar 22 '20 at 20:29
Also, C++ doesn't have [variable-length arrays](https://en.wikipedia.org/wiki/Variable-length_array), use [`std::vector`](https://en.cppreference.com/w/cpp/container/vector) instead. — Some programmer dude, Mar 22 '20 at 20:30
This test case is huge so I can't see the whole test case. But you case my submission here: https://codeforces.com/submissions/niloymahmud# — niloymamhmud, Mar 22 '20 at 20:31
Lastly, please don't use online competition/judge sites as a learning resource, because they're not. Get [a couple of good books](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list/388282#388282) instead, or take classes. — Some programmer dude, Mar 22 '20 at 20:31
I promise you I will not click on an external link to an online judge website. I'm asking if you have access to the test input so that *you* can run the code on *your machine* with that test input and step through the code until it breaks. — JohnFilleau, Mar 22 '20 at 20:32
`long long int d[n];` -- This and other lines that look like this are *not* valid C++. Arrays in C++ must have their sizes denoted by a compile-time constant, not a runtime value. I wouldn't be surprised if your whole program blows up because `n` is large, due to the program blowing out the stack memory. You should be using `std::vector` for dynamic arrays, not fake VLA arrays as you're using now. You're using vector already, so you should be using them here too. — PaulMcKenzie, Mar 22 '20 at 20:37
Then you'll have to generate your own test cases and hope to find one that crashes it. — JohnFilleau, Mar 22 '20 at 20:38
I suggest you post this on the Codeforces forum. The standard for the quality of questions here is pretty high, so you're unlikely to get help unless you include all necessary information in the question itself, including the problem, input, expected output, and actual output. If you don't know the input you'll have to experiment yourself to find a test case that your code fails. You'll also need to rid your code of all the common competitive programming junk, such as `#include ` and `#define tr(niloy,it)` so that non-competitive programmers here can read your code. — eesiraed, Mar 23 '20 at 00:03

score -1 · Accepted Answer · answered Mar 22 '20 at 21:32

The algorithm implementation looks correct for me, the only thing that seems wrong is this line:

d[i] = INT_MAX;

INT_MAX will be 2^32(nearly 10^9) if the compiler uses 32 bit ints, while the max possible real length of optimal solution might be more than that if you have a linear graph like: 1 -> 2 -> 3 -> ... -> n and length of every edge is 10^6. In this case the shortest path will be nearly 10^11 which is more than INT_MAX, meaning that initial values for d array are not really "infinite" as dijkstra's algorithm requires.

Changing initial value to a higher number should fix this issue(10^12 should be enough, but you can use LLONG_MAX as well):

d[i] = 1000000000000; // 10^12

Also, I agree with suggestions in the question comments, use `std::vector` whenever you can. For example here **edge** and **cost** could be vector of vectors: `std::vector>`, that way you can pass them by reference and get sizes using `.size()` function, so you won't need to pass **n** and **m** too. — Cxovrika, Mar 22 '20 at 21:41

Is there any bug in this dijkstra algorithm implementation?

1 Answers1