Bellman Ford Algorithm - Shortest Path from Single Vertex Algorithm

Introduction to Bellman-Ford Algorithm

The Bellman-Ford algorithm is a fundamental algorithm in computer science used for finding the shortest paths from a single source vertex to all other vertices in a weighted graph. Named after Richard Bellman and Lester Ford, who independently developed the algorithm in the late 1950s, it is particularly useful in graphs with negative weight edges, which Dijkstra's algorithm cannot handle.

Why Do We Need the Bellman-Ford Algorithm?

The need for the Bellman-Ford algorithm arises in scenarios where graphs contain negative weight edges. Such edges can represent various real-world situations, such as financial models with losses, transportation systems with detours, or game theory scenarios with penalties. The Bellman-Ford algorithm can detect negative weight cycles, where the total weight of a cycle is negative, leading to infinitely decreasing path weights. This capability makes it a versatile tool in a range of applications.

Working of the Bellman-Ford Algorithm

The Bellman-Ford algorithm finds the shortest paths from a source vertex to all other vertices in a weighted graph, even with negative edge weights. It works by iteratively relaxing edges and propagating distance information through the graph.

For Example: Let's find out the shortest path for every vertex from the source vertex 's' in the given graph.

Graph Representation:

s → (t, 1), (u, 2)
u → (v, 3)
v → (w, -6)
w → (t, -1)
t → (w, -1)

Algorithm Steps:

1. Initialization:
Set distance to source 's' as 0, and all others to infinity.
s: 0, u: ∞, v: ∞, w: ∞, t: ∞

2. Edge Relaxation:
Repeat |V| - 1 times (4 times in this case):

Iteration 1:

• Relax s → u: Update u to 2
• Relax s → t: Update t to 1
• Relax u → v: Update v to 5
• No changes for v → w, w → t, t → w (destinations still ∞)

After Iteration 1: s: 0, u: 2, v: 5, t: 1, w: ∞

Key Observation: v → w is not updated in this iteration because v's distance (5) was just established, and this information hasn't propagated to w yet.

Iteration 2:

• No changes for s → u, s → t
• No change for u → v
• Relax v → w: Update w to -1 (5 + (-6))
• Relax w → t: No change (t already at 1)
• Relax t → w: No change (w already at -1)

After Iteration 2: s: 0, u: 2, v: 5, t: 1, w: -1

Key Observation: v → w is updated in this iteration because v's distance (5) is now known, allowing the algorithm to calculate a path to w through v.

Iteration 3:

• No changes for s → u, s → t, u → v
• No change for v → w
• Relax w → t: Update t to -2 (-1 + (-1))
• No change for t → w

After Iteration 3: s: 0, u: 2, v: 5, t: -2, w: -1

Iteration 4:

• No changes for any edges

After Iteration 4: s: 0, u: 2, v: 5, t: -2, w: -1

3. Negative Cycle Check:
Perform one more relaxation round. If any distance updates occur, it indicates a negative cycle. In this case, no updates occur, so there's no negative cycle.

Final Shortest Paths:
s to s: 0,
s to u: 2,
s to v: 5,
s to t: -2,
s to w: -1

Path Reconstruction:
- Path to u: s → u
- Path to v: s → u → v
- Path to t: s → u → v → w → t
- Path to w: s → u → v → w

Key Insights:

1. The algorithm propagates distance information gradually over iterations. This is why v → w is updated in iteration 2, not iteration 1.
2. Each iteration allows information to spread one edge further from the source.
3. The algorithm correctly handles negative edge weights, finding the optimal path to 't' through 'w', despite the initially shorter direct path from 's'.
4. The |V| - 1 iterations ensure all shortest paths are found in graphs without negative cycles.
5. The final check confirms the absence of negative cycles, as no further updates occur.

This gradual propagation of distance information across iterations is crucial to understanding how the Bellman-Ford algorithm systematically explores all paths, improving distance estimates until optimal solutions are found for all vertices.

How the Bellman-Ford Algorithm Handles Negative Edges

The Bellman-Ford algorithm can handle negative edges by repeatedly checking all edges in the graph:

1. It starts by assuming all distances are very large (infinity), except the starting point.
2. Then, it looks at every edge in the graph multiple times.
3. Each time it looks at an edge, it asks: "Can I make the path to the end of this edge shorter by going through its start?"
4. If the answer is yes, it updates the shortest path to that end point.
5. By doing this many times, it finds the shortest paths even with negative edges.

This is different from Dijkstra's algorithm, which can't handle negative edges because:

• Dijkstra's algorithm assumes that once it finds a path to a point, that path can't get any shorter.
• This assumption doesn't work with negative edges, as they can make paths shorter later on.

By checking all edges multiple times, Bellman-Ford ensures it finds the shortest paths, even when negative edges are present.

Steps in Bellman-Ford Algorithm

The Bellman-Ford algorithm finds the shortest paths from a source vertex to all other vertices in a weighted graph, even with negative edge weights. Here's a detailed breakdown of the algorithm:

1. Initialization

• Set the distance to the source vertex as 0.
• Set the distance to all other vertices as infinity (∞).
• Initialize a predecessor array to keep track of the path.

2. Edge Relaxation

Repeat the following process |V| - 1 times, where |V| is the number of vertices:

• For each edge (u, v) with weight w in the graph:
  • If distance[v] > distance[u] + w, then:
    • Update distance[v] = distance[u] + w
    • Set predecessor[v] = u

Key Point: This step allows the algorithm to gradually propagate distance information through the graph, handling both positive and negative edge weights.

3. Negative Cycle Detection

After the |V| - 1 iterations, perform one more round of relaxation:

• For each edge (u, v) with weight w:
  • If distance[v] > distance[u] + w, then:
    • A negative weight cycle exists
    • The algorithm should terminate and report the cycle

4. Result

• If no negative cycle is detected, the algorithm has found the shortest paths.
• The 'distance' array contains the shortest distance from the source to each vertex.
• The 'predecessor' array can be used to reconstruct the shortest paths.

Pseudo Code

function BellmanFord(Graph, source):
    // Step 1: Initialize distances from source to all vertices as INFINITY and to source itself as 0
    distance[source] = 0
    for each vertex v in Graph:
        if v != source:
            distance[v] = INFINITY

    // Step 2: Relax all edges |V| - 1 times
    for i from 1 to |V|-1:
        for each edge (u, v) in Graph:
            if distance[u] + weight(u, v) < distance[v]:
                distance[v] = distance[u] + weight(u, v)

    // Step 3: Check for negative-weight cycles
    for each edge (u, v) in Graph:
        if distance[u] + weight(u, v) < distance[v]:
            print("Graph contains a negative-weight cycle")
            return

    return distance
        

C++ Code Example with Output

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

struct Edge {
    int source, destination, weight;
};

void BellmanFord(int vertices, int edges, vector<Edge>& graph, int source) {
    vector<int> distance(vertices, INT_MAX);
    distance[source] = 0;

    for (int i = 1; i <= vertices - 1; ++i) {
        for (int j = 0; j < edges; ++j) {
            int u = graph[j].source;
            int v = graph[j].destination;
            int weight = graph[j].weight;
            if (distance[u] != INT_MAX && distance[u] + weight < distance[v]) {
                distance[v] = distance[u] + weight;
            }
        }
    }

    for (int i = 0; i < edges; ++i) {
        int u = graph[i].source;
        int v = graph[i].destination;
        int weight = graph[i].weight;
        if (distance[u] != INT_MAX && distance[u] + weight < distance[v]) {
            cout << "Graph contains a negative-weight cycle" << endl;
            return;
        }
    }

    cout << "Vertex Distance from Source" << endl;
    for (int i = 0; i < vertices; ++i) {
        cout << i << "		" << distance[i] << endl;
    }
}

int main() {
    int vertices = 5;
    int edges = 8;
    vector<Edge> graph(edges);

    graph[0] = {0, 1, -1};
    graph[1] = {0, 2, 4};
    graph[2] = {1, 2, 3};
    graph[3] = {1, 3, 2};
    graph[4] = {1, 4, 2};
    graph[5] = {3, 2, 5};
    graph[6] = {3, 1, 1};
    graph[7] = {4, 3, -3};

    BellmanFord(vertices, edges, graph, 0);

    return 0;
}
        

Output:

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

Time Complexity

The time complexity of the Bellman-Ford algorithm is $O(V \times E)$, where $V$ is the number of vertices and $E$ is the number of edges. This is because the algorithm performs edge relaxation $V-1$ times and each relaxation step involves checking all edges.

Space Complexity

The space complexity of the Bellman-Ford algorithm is $O(V)$, primarily due to the storage of the distance array, which holds the shortest distance from the source to each vertex. Additionally, the graph representation requires $O(E)$ space for storing edges.

Main Uses of Bellman-Ford Algorithm in Detail

→ Network Routing: The algorithm is used in networking to find the shortest paths for data packet transmission, especially in cases where network paths may have negative weights due to various factors like latency or cost.
→ Financial Modeling: It helps in modeling financial scenarios where assets can depreciate in value, or in detecting arbitrage opportunities by identifying negative cycles.
→ Graph Analysis: It aids in analyzing graph structures with potentially negative edges, useful in fields like transportation, logistics, and game theory.

Advantages of Bellman-Ford Algorithm in Detail

→ Handles Negative Weights: Unlike Dijkstra’s algorithm, Bellman-Ford can handle graphs with negative weight edges, making it more versatile.
→ Detects Negative Weight Cycles: It not only finds shortest paths but also identifies negative weight cycles, which can be crucial for ensuring the correctness of various applications.
→ Simplicity: The algorithm is conceptually simple and easy to implement, making it accessible for educational purposes and practical applications.

Disadvantages of Bellman-Ford Algorithm in Detail

→ Slower than Dijkstra's Algorithm: For graphs without negative weights, Dijkstra's algorithm is more efficient, as Bellman-Ford's $O(V \times E)$ time complexity can be considerably slower.
→ Not Optimal for All Graphs: In scenarios where negative weight cycles are absent and performance is critical, other algorithms like Dijkstra's or even more advanced ones like Floyd-Warshall might be preferable.
→ High Iterations: The algorithm requires multiple iterations over all edges, which can be computationally expensive for large graphs.