Introduction

The Bellman-Ford algorithm is a classical algorithm for computing 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 edges, making it more versatile at the cost of higher time complexity. This article explores how the Bellman-Ford algorithm works when the graph is represented as a 2D array (adjacency matrix), with a complete code example and analysis of edge cases.

Graph Representation with a 2D Array

When using a 2D array to represent a graph for Bellman-Ford, the array is the adjacency matrix of the graph:

• Each cell graph[i][j] holds the weight of the edge from vertex $i$ to vertex $j$.
• If there is no edge between vertices $i$ and $j$, the value is set to infinity (or a sentinel value like float('inf') in Python).
• A value of $0$ on the diagonal (graph[i][i]) means the distance from a vertex to itself is zero.

For a graph with $V$ vertices, the adjacency matrix has dimensions $V \times V$.

Algorithm Steps

1. Initialization

Create a distance array dist[] of size $V$:

• Set $\text{dist}[\text{source}] = 0$
• Set $\text{dist}[i] = \infty$ for all other vertices

This means the source is reachable with zero cost, and all other vertices are initially considered unreachable.

2. Relaxation

Iterate $V - 1$ times over all edges. For each edge from vertex $u$ to vertex $v$ with weight $w$:

$$\text{if } \text{dist}[u] + w < \text{dist}[v], \text{ then } \text{dist}[v] = \text{dist}[u] + w$$

When using an adjacency matrix, "iterating over all edges" means scanning every cell graph[u][v] that is not infinity. Each of the $V - 1$ rounds guarantees that shortest paths using at most $k$ edges are found by round $k$.

3. Negative Cycle Detection

After completing the $V - 1$ iterations, perform one additional pass over all edges. If any distance can still be reduced, a negative weight cycle exists in the graph, and shortest paths are not well-defined.

Implementation

Here is a complete Python implementation using a 2D adjacency matrix:

1def bellman_ford(graph: list[list[float]], source: int) -> list[float] | None:
2    v = len(graph)
3    dist = [float('inf')] * v
4    dist[source] = 0
5
6    # Relax all edges V-1 times
7    for _ in range(v - 1):
8        for u in range(v):
9            for w in range(v):
10                if graph[u][w] != float('inf') and dist[u] + graph[u][w] < dist[w]:
11                    dist[w] = dist[u] + graph[u][w]
12
13    # Check for negative weight cycles
14    for u in range(v):
15        for w in range(v):
16            if graph[u][w] != float('inf') and dist[u] + graph[u][w] < dist[w]:
17                return None  # negative cycle detected
18
19    return dist
20
21
22# Example graph (4 vertices)
23INF = float('inf')
24graph = [
25    [0,   4,   INF, INF],
26    [INF, 0,   3,   INF],
27    [INF, INF, 0,   2  ],
28    [INF, -5,  INF, 0  ],
29]
30
31result = bellman_ford(graph, 0)
32if result is None:
33    print("Graph contains a negative weight cycle")
34else:
35    for i, d in enumerate(result):
36        print(f"Distance to vertex {i}: {d}")

Worked Example

Using the graph above with 4 vertices and source vertex 0:

Initial distances: [0, inf, inf, inf]

Round 1:

• Edge $0 \to 1$ (weight 4): $\text{dist}[1] = \min(\infty, 0 + 4) = 4$
• Edge $1 \to 2$ (weight 3): $\text{dist}[2] = \min(\infty, 4 + 3) = 7$
• Edge $2 \to 3$ (weight 2): $\text{dist}[3] = \min(\infty, 7 + 2) = 9$

Round 2:

• Edge $3 \to 1$ (weight -5): $\text{dist}[1] = \min(4, 9 + (-5)) = 4$ (no change)

Round 3: No further updates.

Final distances: [0, 4, 7, 9]

Complexity Analysis

• Time Complexity: $O(V^3)$ when using an adjacency matrix, because scanning all edges requires $O(V^2)$ per round and there are $V - 1$ rounds. With an edge list representation, this becomes $O(V \cdot E)$.
• Space Complexity: $O(V)$ for the distance array (the adjacency matrix is the input and is not counted as extra space).

By comparison, Dijkstra's algorithm with a priority queue achieves $O(V \log V + E)$ but cannot handle negative edge weights.

When to Use Bellman-Ford

• The graph contains negative weight edges (Dijkstra fails here).
• You need to detect negative weight cycles.
• The graph is dense enough that the adjacency matrix representation is natural.

For sparse graphs without negative weights, Dijkstra with a min-heap is the better choice.

Common Pitfalls

• Forgetting to initialize the source distance to zero.
• Using an adjacency matrix but not skipping infinity entries during relaxation, which leads to integer overflow issues.
• Running only one pass instead of $V - 1$ passes, which misses shortest paths that use many edges.
• Confusing "no path exists" (distance remains infinity) with "negative cycle detected" (distance keeps decreasing).

Summary

The Bellman-Ford algorithm finds shortest paths from a single source in graphs that may contain negative weights. When the graph is stored as a 2D adjacency matrix, the triple-nested loop structure is straightforward but runs in $O(V^3)$ time. The algorithm's ability to detect negative cycles makes it uniquely valuable compared to Dijkstra's algorithm, at the cost of higher time complexity.