Working of Bellman-Ford Algorithm to Detect the Negative cycle in the graph
Let’s suppose we have a graph which is given below and we want to find whether there exists a negative cycle or not using Bellman-Ford.
Step 1: Initialize a distance array Dist[] to store the shortest distance for each vertex from the source vertex. Initially distance of source will be 0 and Distance of other vertices will be INFINITY.
Step 2: Start relaxing the edges, during 1st Relaxation:
Step 3: During 2nd Relaxation:
- Current Distance of B > (Distance of A) + (Weight of A to B) i.e. Infinity > 0 + 5
- Therefore, Dist[B] = 5
- Current Distance of D > (Distance of B) + (Weight of B to D) i.e. Infinity > 5 + 2
- Dist[D] = 7
- Current Distance of C > (Distance of B) + (Weight of B to C) i.e. Infinity > 5 + 1
- Dist[C] = 6
Step 4: During 3rd Relaxation:
- Current Distance of F > (Distance of D ) + (Weight of D to F) i.e. Infinity > 7 + 2
- Dist[F] = 9
- Current Distance of E > (Distance of C ) + (Weight of C to E) i.e. Infinity > 6 + 1
- Dist[E] = 7
Step 5: During 4th Relaxation:
- Current Distance of D > (Distance of E) + (Weight of E to D) i.e. 7 > 7 + (-1)
- Dist[D] = 6
- Current Distance of E > (Distance of F ) + (Weight of F to E) i.e. 7 > 9 + (-3)
- Dist[E] = 6
Step 6: During 5th Relaxation:
- Current Distance of F > (Distance of D) + (Weight of D to F) i.e. 9 > 6 + 2
- Dist[F] = 8
- Current Distance of D > (Distance of E ) + (Weight of E to D) i.e. 6 > 6 + (-1)
- Dist[D] = 5
- Since the graph h 6 vertices, So during the 5th relaxation the shortest distance for all the vertices should have been calculated.
Step 7: Now the final relaxation i.e. the 6th relaxation should indicate the presence of negative cycle if there is any changes in the distance array of 5th relaxation.
During the 6th relaxation, following changes can be seen:
- Current Distance of E > (Distance of F) + (Weight of F to E) i.e. 6 > 8 + (-3)
- Dist[E]=5
- Current Distance of F > (Distance of D ) + (Weight of D to F) i.e. 8 > 5 + 2
- Dist[F]=7
Since, we observer changes in the Distance array Hence ,we can conclude the presence of a negative cycle in the graph.
Result: A negative cycle (D->F->E) exists in the graph.
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