Bellman ford algorithm | Negative Weight Cycle

What is the Bellman ford algorithm?

The Bellman ford algorithm is one type of single-source shortest path algorithm. This algorithm is used to find the shortest path of a weighted graph even if there are negative cycles exist.

The question is Dijkstra algorithm is also a single-source shortest path algorithm. Then why do we need the Bellman ford algorithm? 

There is some drawback of the Dijkstra algorithm. As we know the Dijkstra algorithm can't be applicable for the negative value graph, especially where the negative cycle exists. The advantage of the bellman ford algorithm over the Dijkstra algorithm is that it is capable to work with negative cycle values graphs. That is the specialty of this algorithm. And the disadvantage of the bellman ford algorithm over the Dijkstra algorithm is that the time complexity of bellman for the algorithm is very high than the Dijkstra algorithm. So, the Dijkstra algorithm is faster than the bellman ford algorithm.


Negative Weight Cycle

When the edges nodes values sum is negative and the nodes create a cycle for a directed graph, then it can be called as Negative Weight Cycle. A Negative Weight Cycle has generally seen in the directed graph. This type of cycle can be handled using the Bellman-Ford algorithm. The Negative Weight Cycle shows in below figure 01.

Negative Weight Cycle

Fig. 01: Negative Weight Cycle in the figure (circled arrow)

Read Similar Post: 

1. Dijkstra Time Complexity

2. Kushkal's Algorithm Application and Disjoint Set

Post a Comment

Previous Post Next Post