Why do Shortest Path Algorithms fail in Graphs with Negative Cycle?

Algorithms

The shortest path algorithms such as Dijkstra and Bellman-Ford algorithm don’t give the right results when there’s a negative cycle in the graph.

Dijkstra’s AlgorithmBellman-Ford Algorithm
Graph with Negative EdgeFailsPass
Graph with Negative CycleFailsFails

Recommended read: Why doesn’t Dijkstra’s algorithm work in graphs with negative-weighted edges?

Although Bellman-Ford works with negative edges, it still fails to deliver the correct results (i.e. the shortest route) in case of the graphs with negative cycles.

Consider the following graph with a negative cycle:

Graph with a negative cycle

What do you think is the shortest route from A to F?

You may say A->B->C->D->E->B->C->F (Distance = 15), but that’s not correct..

The answer is that no optimal path exists from A to F due to the presence of a negative cycle.

The overall distance of the cycle B->C->D->E->B is -5. The more we repeat the cycle, the more the distance of the path decreases i.e. A->(B->C->D->E->B)n-times->C->F (Distance = -∞).

That’s why most of the algorithms run into ambiguity while dealing with negative cycles and fail as a result.

In such cases, it’s best to use the Bellman-Ford algorithm. It may not get results but can detect negative cycles.

I hope now it is clear to you now, how negative cycles causes the algorithm to fail to calculate the shortest path in a given graph.

Leave a Reply

Your email address will not be published. Required fields are marked *