Grokking Graph Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Bellman–Ford Algorithm
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

The Bellman-Ford algorithm is a well-known algorithm for finding the shortest paths from a single source vertex to all other vertices in a weighted graph. Unlike Dijkstra's algorithm, Bellman-Ford can handle graphs with negative weight.

Key Features

  • Single Source Shortest Path: Finds the shortest path from a single source vertex to all other vertices in the graph.
  • Negative Weight Edges: Can handle graphs with negative weight edges, unlike Dijkstra's algorithm.
  • Cycle Detection: Detects negative weight cycles in the graph, which can indicate an inconsistency in the graph's weights.

Steps

  1. Initialization: Set the distance to the source vertex to zero and all other vertices to infinity.
  2. Relaxation: Iteratively relax all edges (V-1) times, where (V) is the number of vertices. This ensures that the shortest paths are found.
  3. Negative Cycle Check: Perform one more iteration to check for negative weight cycles. If a shorter path is found, it indicates the presence of a negative weight cycle.

Overall, the Bellman-Ford algorithm is a powerful tool for finding shortest paths in graphs, particularly when negative weights are involved. It is widely used in network routing protocols and other applications where the shortest path needs to be determined in the presence of negative weights.

Step-by-Step Algorithm

  1. Initialize Distances:

    • Set the distance to the source vertex to 0.
    • Set the distance to all other vertices to infinity.

  2. Relax All Edges:

    • Repeat (V-1) times (where (V) is the number of vertices):
      • For each edge (u, v) with weight w:
        • If the distance to vertex u is not infinity and the distance to vertex v through u is shorter than the current distance to v:
          • Update the distance to vertex v.

  3. Check for Negative Weight Cycles:

    • For each edge (u, v) with weight w:
      • If the distance to vertex u is not infinity and the distance to vertex v through u is shorter than the current distance to v:
        • Report that the graph contains a negative weight cycle.

  4. Print Results:

    • Print the shortest distances from the source to all vertices.

Algorithm Walkthrough

Consider the example used in the code with the following edges and weights:

Edges: (0-1, -1), (0-2, 4), (1-2, 3), (1-3, 2), (1-4, 2), (3-2, 5), (3-1, 1), (4-3, -3)
Vertices: 5 (0, 1, 2, 3, 4)
Image

  1. Initialize Distances:

    dist[] = [0, ∞, ∞, ∞, ∞] (Distance from source vertex 0 to itself is 0)

  2. Relax All Edges (V-1 = 4) times:

    • First Iteration:

      • Relax edge (0-1, -1): 
        dist[1] = min(∞, 0 + (-1)) = -1
dist[] = [0, -1, ∞, ∞, ∞]
      • Relax edge (0-2, 4): 
        dist[2] = min(∞, 0 + 4) = 4
dist[] = [0, -1, 4, ∞, ∞]
      • Relax edge (1-2, 3): 
        dist[2] = min(4, -1 + 3) = 2
dist[] = [0, -1, 2, ∞, ∞]
      • Relax edge (1-3, 2): 
        dist[3] = min(∞, -1 + 2) = 1
dist[] = [0, -1, 2, 1, ∞]
      • Relax edge (1-4, 2): 
        dist[4] = min(∞, -1 + 2) = 1
dist[] = [0, -1, 2, 1, 1]
      • Relax edge (3-2, 5): 
        dist[2] = min(2, 1 + 5) = 2
dist[] = [0, -1, 2, 1, 1]
      • Relax edge (3-1, 1): 
        dist[1] = min(-1, 1 + 1) = -1
dist[] = [0, -1, 2, 1, 1]
      • Relax edge (4-3, -3): 
        dist[3] = min(1, 1 + (-3)) = -2
dist[] = [0, -1, 2, -2, 1]

    • Second Iteration:

      • Relax edge (0-1, -1): 
        dist[1] = min(-1, 0 + (-1)) = -1
dist[] = [0, -1, 2, -2, 1]
      • Relax edge (0-2, 4): 
        dist[2] = min(2, 0 + 4) = 2
dist[] = [0, -1, 2, -2, 1]
      • Relax edge (1-2, 3): 
        dist[2] = min(2, -1 + 3) = 2
dist[] = [0, -1, 2, -2, 1]
      • Relax edge (1-3, 2): 
        dist[3] = min(-2, -1 + 2) = -2
dist[] = [0, -1, 2, -2, 1]
      • Relax edge (1-4, 2): 
        dist[4] = min(1, -1 + 2) = 1
dist[] = [0, -1, 2, -2, 1]
      • Relax edge (3-2, 5): 
        dist[2] = min(2, -2 + 5) = 2
dist[] = [0, -1, 2, -2, 1]
      • Relax edge (3-1, 1): 
        dist[1] = min(-1, -2 + 1) = -1
dist[] = [0, -1, 2, -2, 1]
      • Relax edge (4-3, -3): 
        dist[3] = min(-2, 1 + (-3)) = -2
dist[] = [0, -1, 2, -2, 1]

    • Third Iteration:

      • All relaxations will result in the same distances as the previous iteration.

    • Fourth Iteration:

      • All relaxations will result in the same distances as the previous iteration.

  3. Check for Negative Weight Cycles:

    • None of the edges can provide a shorter path, indicating no negative weight cycles.

  4. Final Distances:

    Vertex Distance from Source
0  0
1  -1
2  2
3  -2
4  1

Code

Python3
Python3
. . . .

Complexity Analysis

Time Complexity

  1. Initialization: Initializing the distance array takes O(V) time.
  2. Relaxation: The nested loops for relaxing all edges (V-1) times take O(V \cdot E) time.
  3. Negative Cycle Check: Checking for negative weight cycles takes O(E) time.

Thus, the overall time complexity of the Bellman-Ford algorithm is O(V \cdot E).

Space Complexity

  1. Distance Array: Storing the distance of each vertex requires O(V) space.
  2. Edge List: Storing all edges requires O(E) space.

Thus, the overall space complexity is O(V + E).

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible