Bellman-Ford Algorithm

The Bellman-Ford Algorithm is a graph algorithm used to find the shortest path from a single source vertex to all other vertices in a weighted graph. It is particularly useful when the graph contains negative weight edges.

Algorithm Steps

1. Initialize distances:
   • Set the distance to the source vertex as 0 and all other vertices as ∞ (infinity).
2. Relax edges (V - 1) times:
   • Iterate over all edges and update the distance to each vertex if a shorter path is found.
3. Check for negative-weight cycles:
   • Run one more iteration over all edges.
   • If any distance can still be reduced, the graph contains a negative-weight cycle.

Complexity Analysis

Time Complexity:

• The algorithm runs (V - 1) iterations, where each iteration processes E edges.
• This results in a time complexity of O(VE), making it slower than Dijkstra's algorithm for dense graphs.

Space Complexity:

• The algorithm requires an array to store distances, leading to a space complexity of O(V).

Applications

Detecting Negative-Weight Cycles

The Bellman-Ford algorithm can detect negative-weight cycles, which are cycles in a graph where the sum of edge weights is negative. If such a cycle exists, the algorithm reports it, preventing incorrect shortest path calculations.

Shortest Path Calculation

Bellman-Ford is useful for finding the shortest path in graphs that contain negative-weight edges, unlike Dijkstra’s algorithm, which fails with negative weights.

Routing Protocols

The algorithm is used in network routing protocols such as RIP (Routing Information Protocol) to find the shortest paths in a network.

Example Graph

Consider the following weighted directed graph:                        

                                A --(4)--> B                                 A --(1)--> C                                 B --(-2)--> C                                 C --(2)--> D

If A is the source vertex, the Bellman-Ford algorithm computes the shortest paths from A to all other vertices, considering both positive and negative edge weights.

OUTPUT: Shortest distances from source 0: To vertex 0 is 0 To vertex 1 is 6 To vertex 2 is 7 To vertex 3 is 2 To vertex 4 is 4