Here is my code for Dijkstra’s algorithm. I am getting the correct output for few examples with negative weights. So please explain it can work in case of negative edges or not in the case of directed graphs
void dijkstra(int src, int n){
vector distance(n,INT_MAX);
distance[src]=0;
priority_queue< pair<int, int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
pq.push({0, src}); // in pq we are storing first dist and then node
while(!pq.empty()){
int dist = pq.top().first;
int prev = pq.top().second;
pq.pop();
vector<pair<int,int>>:: iterator it;
for(it = adj[prev].begin(); it!=adj[prev].end(); it++){
int next = it->first;
int next_dist = it->second;
if((dist + next_dist )<distance[next]){
distance[next] = (dist + next_dist);
pq.push({distance[next], next});
}
}
}
for(int i=0; i<n; i++) cout<<distance[i]<<" ";
}
Please help I am a beginner.
Actually , Dijkstra’s algorithm fails to work for most of the negative weight edged graphs , but sometimes it works with some of the graphs with negative weighted edges too provided the graph doesn’t have negative weight cycles , This is one case in which dijkstra’s algorithm works fine and finds the shortest path between whatever the point u give
And adding some positive number X to all the edges just to make them positive doesn’t result in correct answer. Shortest distance can be P through one path and P1 through another path containing number of edges N and N1 respectively , suppose P > P1 but P1 has more edges than P , that might actually make P less than P1 since P’s distance is added to N * whatever the actual number u added to all the edges and thus results in a wrong answer!!
edit: Yes , Dijkstra also works for some of the graphs with negative weighted cycle too as long as the element that is already considered shortest is not relaxed anymore.
2 Likes
thanks a lot for such a grt exp. Sir if possible could you explain your point with some example in which we are adding some number to make positive weights. It would be very helpful.