Help needed in dijkstra's algo implementation

Can somebody tell why this code is giving runtime error?
Thanks in advance
#include
#include
#include<bits/stdc++.h>
using namespace std;
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mod 1000000000000
#define test ll t; t=1; while(t–)
typedef long long int ll;
void dijakstra(vector<vector<pair<ll,ll>>>adj,vectord,vectorp,ll s,ll n){
d.assign(n,mod);
p.assign(n,-1);
set<pair<ll,ll>>q;
q.insert({0,s});
d[s]=0;
while(!q.empty()){
ll v,to,len;
v=q.begin()->second;
q.erase(q.begin());
for(auto i:adj[v]) {
to=i.first;
len=i.second;
if(d[to]>d[v]+len){
d[to]=d[v]+len;
p[to]=v;
q.insert({d[to],to});
}
}
}
}
int main() {
FIO;
test{
vector<vector<pair<ll,ll>>> adj;
ll n,m,i,l,r,w,s;
cin>>n>>m;
cin>>s;
for(i=0;i<m;i++){
cin>>l>>r>>w;
adj[l].push_back(make_pair(r,w));
adj[r].push_back(make_pair(l,w));
}
vectord;
vectorp;
dijakstra(adj,d,p,0,n);
for(i=0;i<n;i++){
cout<<i<<" "<<d[i]<<endl;
}
}
return 0;
}

Please format your code - the forum software has mangled it and it won’t compile! :slight_smile:

Also - what test input is causing the runtime error?

1 Like
#include <iostream>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mod 1000000000000
#define test ll t; t=1; while(t--)
typedef long long int ll;
void dijakstra(vector<vector<pair<ll,ll>>>adj,vector<ll>d,vector<ll>p,ll s,ll n){
    d.assign(n,mod);
    p.assign(n,-1);
    set<pair<ll,ll>>q;
    q.insert({0,s});
    d[s]=0;
    while(!q.empty()){
        ll v,to,len;
        v=q.begin()->second;
        q.erase(q.begin());
        for(auto i:adj[v]) {
            to=i.first;
            len=i.second;
            if(d[to]>d[v]+len){
                d[to]=d[v]+len;
                p[to]=v;
                q.insert({d[to],to});
            }
        }
    }
}
int main() {
    FIO;
    test{
        vector<vector<pair<ll,ll>>> adj;
        ll n,m,i,l,r,w,s;
        cin>>n>>m;
        cin>>s;
        for(i=0;i<m;i++){
            cin>>l>>r>>w;
            adj[l].push_back(make_pair(r,w));
            adj[r].push_back(make_pair(l,w));
        }
        vector<ll>d;
        vector<ll>p;
        dijakstra(adj,d,p,0,n);
        for(i=0;i<n;i++){
            cout<<i<<" "<<d[i]<<endl;
        }
    }
	return 0;
}
1 Like

Test case:
9 14
0
0 1 4
0 7 8
1 2 8
1 7 11
2 3 7
2 8 2
2 5 4
3 4 9
3 5 14
4 5 10
5 6 2
6 7 1
6 8 6
7 8 7

First error, line 39:

 adj[l].push_back(make_pair(r,w));
 ^    ^

adj is still empty, so adj[l] is an out-of-bounds access.

2 Likes

As ssjgz pointed out you need to use

vector<vector<int>> adj(n);

To initialise with n vectors.
But i like using

vector<int> adj[n];
3 Likes

Bro do u have codes for basic algos of graph theory like flyod warshall,Belleman ford etc

CP Algorithms contains implementations of many standard algos.

Can we add a large constant to the edges to perform dijikstra instead of belmanford?

Then you even need to keep track of no of edges you have processed as you need to subtract that constant back from each edge

1 Like

Thanks a lot. :slight_smile:

1 Like

No @dean_student that is not true. Adding a large constant incentivises shorter length rather than distance. For example consider the graph from 1 to 4.


Over here if you add a large constant, it will disproportionally affect the shorter route, by 3 times.

A constant of 3 is enough to change the answer to 6, and the shorter path will have a distance of 7. Even after subtracting 3 after the search we’ll get 3. Which is incorrect, as the answer is actually -2.

2 Likes

Got it bro , thanks :slight_smile:

Bro can’t it be done once we keep track of no of edges like in shortest path we get 6 which is 6-3 and 7 in another path which is actually 7-3*3=-2
But it will be diffficult to maintain set

Then it loses it’s time conplexity.