Shortest Path Algorithm: Bellman-Ford Algorithm

Bellman-Ford Algorithm is an algorithm used to compute single-source shortest paths in a weighted directed graph. Unlike Dijkstra's Algorithm, Bellman-Ford can handle graphs containing edges with negative weights and can detect the existence of negative-weight cycles within the graph.

1. Problem Description and Core Idea

Suppose we have a weighted directed graph G(V, E), where V is the set of vertices and E is the set of edges. Given a source vertex s, our goal is to find the shortest path weights from s to all other vertices in the graph. If there exists a reachable negative-weight cycle from s, then some shortest paths may not exist (i.e., the path weight can be decreased indefinitely).

The core idea of the Bellman-Ford Algorithm is straightforward: through the Relaxation operation, it systematically considers all edges to gradually approximate the solution for the shortest paths. It guarantees finding the shortest paths (if they exist) by performing |V|-1 rounds of relaxation operations on all edges.

2. Key Concept: Relaxation Operation

The relaxation operation is the foundation of the Bellman-Ford (and Dijkstra's) algorithm. For an edge pointing from vertex u to vertex v with weight w, the relaxation process is as follows:

Assume we know a current estimated distance dist[u] from source s to vertex u, and a current estimated distance dist[v] from s to v. The relaxation operation checks whether a shorter path to v can be obtained by going through u.

Specific steps:

1. Check condition: dist[u] + w(u, v) < dist[v]
2. If the condition is true, it means we have found a shorter path to v (i.e., s -> ... -> u -> v).
3. We then update the value of dist[v]: dist[v] = dist[u] + w(u, v)
4. Typically, we also record the predecessor of v as u to later reconstruct the shortest path.

3. Detailed Algorithm Steps

The execution of the Bellman-Ford Algorithm can be clearly divided into two main phases.

Phase One: Initialization and Relaxation

1. Initialization:

   • Create an array dist[] of size |V| to store the estimated shortest distance from source s to each vertex.
   • Set dist[s] to 0, indicating the distance from s to itself is 0.
   • Set dist[v] for all other vertices to a very large value (e.g., Infinity), indicating initially we know of no path to these vertices.

2. Core Relaxation Loop:

   • Perform |V| - 1 rounds of relaxation operations on all edges of the graph.
   • In each round, we iterate through every edge (u, v) in the graph and attempt to relax it.
   • Why |V| - 1 rounds? Because in a shortest path that does not contain a negative-weight cycle, there are at most |V| - 1 edges. After |V| - 1 rounds of relaxing all edges, it is sufficient to guarantee that the shortest path information "propagates" from source s to all reachable vertices.

Phase Two: Negative-weight Cycle Detection

After completing |V| - 1 rounds of relaxation, the shortest paths are theoretically obtained. However, to handle negative-weight cycles, an additional check is needed.

3. Detect Negative-weight Cycles:
   • Traverse every edge (u, v) in the graph once more.
   • For each edge, check if a relaxation operation is still possible. That is, check if dist[u] + w(u, v) < dist[v] still holds.
   • If the above condition holds for any edge, then it indicates the graph contains a reachable negative-weight cycle from s. Because only with a negative-weight cycle can the path weight be decreased indefinitely, preventing the relaxation process from ever stopping.
   • If a negative-weight cycle is detected, the algorithm reports "Graph contains a negative-weight cycle," rendering shortest paths meaningless.
   • If no negative-weight cycle is detected, then the dist[] array stores the lengths of the shortest paths from source s to each vertex.

4. A Simple Example

Consider a simple directed graph with vertices A, B, C, and source A.
Edges: A->B (weight 4), A->C (weight 5), B->C (weight -2)

• Initialization: dist[A]=0, dist[B]=Inf, dist[C]=Inf
• First Round Relaxation (process all edges):
  • Process A->B: 0+4 < Inf => update dist[B]=4
  • Process A->C: 0+5 < Inf => update dist[C]=5
  • Process B->C: 4+(-2)=2 < 5 => update dist[C]=2
• (Since |V|=3, we only need 2 rounds of relaxation. But the result is already stable after the first round.)
• Second Round Relaxation: Process all edges again, finding no distance values can be updated further.
• Negative-weight Cycle Detection: Check all edges again; no case of dist[u] + w < dist[v] is found. Therefore, no negative-weight cycle exists.
• Final Result: The shortest distance from A to B is 4, and from A to C is 2.

5. Time and Space Complexity Analysis

• Time Complexity: O(|V| * |E|). The algorithm performs |V| - 1 loop rounds, each round iterating through all |E| edges. Negative-weight cycle detection also requires traversing all edges, with complexity O(|E|). Thus the total complexity is O(|V||E| + |E|) = O(|V||E|). This is acceptable for dense graphs (where edge count is close to |V|²), but for sparse graphs, it is less efficient than Dijkstra's Algorithm.
• Space Complexity: O(|V|). The main space is used to store the dist[] array and the predecessor array.

6. Summary and Comparison

The Bellman-Ford Algorithm is irreplaceable in certain scenarios due to its robustness, such as when calculating paths in routing protocols where negative weights might be encountered (though uncommon), or when we need to ensure the network has no negative-weight cycles that could cause infinite loops.