Error in Dijkstra's shortest path algorithm implementation (using C++ STL)

Question

I have tried to implement Dijkstra's algorithm in C++ using std::priority_queue.The function "dijsktra" will take input as 2 nodes, the source vertex and the destination vertex. However, I am getting incorrect answers every time. Kindly help me out and tell me where I have erred. My code-

#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <stdio.h>
#include <vector>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#define inf 9999999
using namespace std;

map <int,int> vis;
vector <vector <pair <int,int> > > adj(100);
vector <int> dist(100);

void dijkstra(int u,int t)
{
    priority_queue <pair <int,int> > q;
    int b,w,i;
    q.push({0,u});
    vis[u]=1;
    
    while(!q.empty())
    {
        u = q.top().second; q.pop();
        
        if(!vis[u])
        {
            vis[u]=1;
            for(i=0;i<adj[u].size();i++)
            {
                b = adj[u][i].first; w = adj[u][i].second;
                if(dist[b]>dist[u]+w)
                {
                    dist[b] = dist[u] + w;
                    q.push({-dist[b],b});
                }
            }
        }
    }
    
    cout << dist[t];
}


int main()
{
    int i,j,k,n,m,x,y,w,t;
    
    cin >> n >> m;
    for(i=0;i<m;i++)
    {
        cin >> x >> y >> w;
        adj[x].push_back({y,w});
        adj[y].push_back({x,w});
    }
    
    cin >> t;
    
    for(i=1;i<=n;i++)
    {
        dist[i]=inf;
    }
    
    dijkstra(1,t);
}

@SaiSreenivas I tried that, I am still getting wrong output (now output is INT_MAX). Priority queue returns the maximum element but I want the minimum element, that is why I am sending -dist[b]. — vvdalimkar
– vvdalimkar, Commented Jul 26, 2020 at 12:20

Sai · Accepted Answer · 2020-07-26 13:10:02Z

Mistake:

Your code is not working due to vis[u] = 1 which never lets you enter the for loop.

Actually there is no need of having a visited array in Dijkstra algorithm (atleast for this case). But using visited array here will decrease the time complexity and when there are negative edges it will be tricky, so be careful there.

#include <iostream>
#include <vector>
#include <queue>
#define inf 9999999

std::vector <std::vector <std::pair <int,int> > > adj(100);
std::vector <int> dist(100);

void dijkstra(int u,int t)
{
    std::priority_queue <std::pair<int, int>> q;
    int b, w, i;

    q.push({0, u});
    while(!q.empty()) {
        u = q.top().second; 
        q.pop();
        for(i = 0; i < adj[u].size(); i++) {
            b = adj[u][i].first; w = adj[u][i].second;
            if(dist[b] > dist[u] + w) {
                dist[b] = dist[u] + w;
                q.push({-dist[b], b});
            }
        }
    }
    
    std::cout << dist[t];
}


int main()
{
    int i, n, m, x, y, w, t;
    
    std::cin >> n >> m;
    for(i = 0;i < m; i++) {
        std::cin >> x >> y >> w;
        adj[x].push_back({y, w});
        adj[y].push_back({x, w});
    }
    
    std::cin >> t;
    
    for(i = 0; i < n; i++) {
        dist[i] = inf;
    }
     
    // making the source distance to 0
    dist[0] = 0;
    
    dijkstra(0,t);
}

MikeCAT · Accepted Answer · 2020-07-26 12:35:04Z

1

The problem is vis[u]=1; just after q.push({0,u});.

Due to that, the check if(!vis[u]) cannot be passed and no nodes will be processed.

You should do dist[u]=0; instead of that.

answered Jul 26, 2020 at 12:35

MikeCAT

75.1k11 gold badges50 silver badges71 bronze badges

Collectives™ on Stack Overflow

Error in Dijkstra's shortest path algorithm implementation (using C++ STL)

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related