Question

1- Can Dijkstra's algorithm handle negative edges cycles? Why/Why not? If not, is there any alternative algorithms that can compute the shortest path for a graph with negative cycles?

Answer 1

As per your requirement i have written solution which fulfill all your requirements please follow it step by step

No,Actually Dijkstra's algorithm cannot handle negative edges cycles.Let see that clearly

Recall that in Dijkstra's algorithm, once a vertex is marked as "closed" (and out of the open set) - the algorithm found the shortest path to it, and will never have to develop this node again it assumes the path developed to this path is the shortest. But with negative weights - it might not be true. For example:

2 B--(-10)--〉C Vr(A, B,C) ; E {(A, C,2), (A, B,5), (B,C,-10)} Dijkstra from A will first develop C, and will later fail to find A->B->C

So for that We can find shortest path in graph that has negative weight cycles using Bellman–Ford Algorithm

Let see that clearly step by step through algorithm

Algorithnm Following are the detailed steps. Input: Graph and a source vertex src Output: Shortest distance to all vertices from src. If there is a negative weight cycle, then short- est distances are not calculated, negative weight cycle is reported. 1) This step initializes distances from source to all vertices as infinite and distance to source it- self as 0. Create an array distl of size IVI with all values as infinite except dist src] where src is source vertex.

2) This step calculates shortest distances. Do following IVI-1 times where IVI is the number of vertices in given graph. .....a) Do following for each edge u-v . . . .If dist[v] > dist[ul + weight of edge uv, then update dist[v]

3) This step reports if there is a negative weight cycle in graph. Do following for each edge u-v .....If distivl]> dist[u] + weight of edge uv, then "Graph contains negative weight cycle" The idea of step 3 is, step 2 guarantees shortest distances if graph doesn't contain negative weight cycle. If we iterate through all edges one more time and get a shorter path for any ver- tex, then there is a negative weight cycle

By this we have found solution for Can Dijkstra's algorithm handle negative edges cycles? Why/Why not? If not, is there any alternative algorithms that can compute the shortest path for a graph with negative cycles.