Algorithm to Find Negative Cycle in a Directed Weighted Graph Using Bellman-Ford
- Initialize distance array dist[] for each vertex ‘v‘ as dist[v] = INFINITY.
- Assume any vertex (let’s say ‘0’) as source and assign dist = 0.
- Relax all the edges(u,v,weight) N-1 times as per the below condition:
- dist[v] = minimum(dist[v], distance[u] + weight)
- Now, Relax all the edges one more time i.e. the Nth time and based on the below two cases we can detect the negative cycle:
- Case 1 (Negative cycle exists): For any edge(u, v, weight), if dist[u] + weight < dist[v]
- Case 2 (No Negative cycle) : case 1 fails for all the edges.
Bellman–Ford Algorithm
Imagine you have a map with different cities connected by roads, each road having a certain distance. The Bellman–Ford algorithm is like a guide that helps you find the shortest path from one city to all other cities, even if some roads have negative lengths. It’s like a GPS for computers, useful for figuring out the quickest way to get from one point to another in a network. In this article, we’ll take a closer look at how this algorithm works and why it’s so handy in solving everyday problems.
Table of Content
- Bellman-Ford Algorithm
- The idea behind Bellman Ford Algorithm
- Principle of Relaxation of Edges for Bellman-Ford
- Why Relaxing Edges N-1 times, gives us Single Source Shortest Path?
- Why Does the Reduction of Distance in the N’th Relaxation Indicates the Existence of a Negative Cycle?
- Working of Bellman-Ford Algorithm to Detect the Negative cycle in the graph
- Algorithm to Find Negative Cycle in a Directed Weighted Graph Using Bellman-Ford
- Handling Disconnected Graphs in the Algorithm
- Complexity Analysis of Bellman-Ford Algorithm
- Bellman Ford’s Algorithm Applications
- Drawback of Bellman Ford’s Algorithm
Contact Us