This dijkstra code isn't working for Directed graphs
For example for this testcase:
4
2
1
7
1 2 1
1 3 1
2 1 1
2 4 1
3 1 1
3 4 1
4 3 1
Click to view Graph diagram for above testcase
Edge 2 -> 4 is only one way while the algorithm behaves as if it is 2-way. Shortest path between 4 to 2 should be 3 while the following code gives 1 output :
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
const int INF = 1e9+10;
vector<pair<int,int>> g[N];
vector<int> vis(N,0);
vector<int> dist(N, INF);
void bfs(int source){
set<pair<int,int>> st;
st.insert({0,source});
dist[source] = 0;
while(st.size()>0){
auto curr = *st.begin();
int wt_v = curr.first;
int v = curr.second;
st.erase(st.begin());
if(vis[v]) continue;
vis[v] = 1;
for(auto child:g[v]){
int child_v = child.first;
int wt = child.second;
if(dist[v] + wt < dist[child_v]){
dist[child_v] = dist[v] + wt;
st.insert({dist[child_v],child_v});
}
}
}
}
int main(){
int n; cin>>n;
int e; cin>>e;
int t; cin>>t;
int m; cin>>m;
for (int i = 0; i < m; ++i){
int v1,v2,wt; cin>>v1>>v2>>wt;
g[v1].push_back({v2,wt});
}
bfs(e);
for (int i = 1; i <= n; ++i){
cout<<dist[i]<<endl;
}
}
If you want 4 to 2, then you have to change your input. The second line should be 4
As is, your output is hard to comprehend. Lets's do this
bfs(e);
for (int i = 1; i <= n; ++i){
cout<<"dist from " << e << " to " <<i
<< " is " <<dist[i]<<endl;
So now, input of this
4
4
1
7
1 2 1
1 3 1
2 1 1
2 4 1
3 1 1
3 4 1
4 3 1
output is
dist from 4 to 1 is 2
dist from 4 to 2 is 3
dist from 4 to 3 is 1
dist from 4 to 4 is 0