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 Algorithm | Bellman-Ford Algorithm | |
---|---|---|

Graph with Negative Edge | Fails | Pass |

Graph with Negative Cycle | Fails | Fails |

**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:

**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.