# Shortest Path in Weighted Graph: Bellman-Ford Algorithm

Source: https://www.techinterview.org/post/3233460137/shortest-path-in-weighted-graph-bellman-ford-algorithm/
Updated: 2026-04-16 · techinterview.org

Bellman-Ford is the shortest-path algorithm you reach for when Dijkstra fails — specifically when graphs contain negative-weight edges or you need to detect negative cycles. It appears in finance (arbitrage detection), routing protocols (RIP), and interviews at companies asking about weighted graph problems.

## When to Use Bellman-Ford vs Dijkstra

| Criterion | Dijkstra | Bellman-Ford |
| --- | --- | --- |
| Negative edge weights | Fails (greedy assumption broken) | Handles correctly |
| Negative cycles | Cannot detect | Detects explicitly |
| Time complexity | O((V + E) log V) with min-heap | O(V * E) |
| When to use | Non-negative weights, performance-critical | Negative weights or cycle detection needed |

## How Bellman-Ford Works

Key insight: any shortest path in a graph with V vertices has at most V-1 edges (if it had V or more, it would visit a vertex twice — a cycle). So we relax all edges V-1 times. After V-1 iterations, if we can still relax any edge, a negative cycle exists.


```
def bellman_ford(n: int, edges: list[tuple], src: int) -> tuple[list[float], bool]:
    """
    Bellman-Ford shortest path from src to all vertices.

    edges: list of (u, v, weight)
    Returns: (dist[], has_negative_cycle)
    Time: O(V * E), Space: O(V)
    """
    INF = float('inf')
    dist = [INF] * n
    dist[src] = 0

    # Relax all edges V-1 times
    for _ in range(n - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        if not updated:
            break  # Early termination if no updates

    # V-th relaxation: if anything updates, negative cycle exists
    has_negative_cycle = False
    for u, v, w in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:
            has_negative_cycle = True
            break

    return dist, has_negative_cycle

# Example: graph with 5 vertices
n = 5
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),
]
dist, cycle = bellman_ford(n, edges, src=0)
print(f"Distances from 0: {dist}")  # [0, -1, 2, -2, 1]
print(f"Negative cycle: {cycle}")   # False
```


## Reconstructing the Path


```
def bellman_ford_with_path(n: int, edges: list[tuple], src: int, dst: int):
    """Returns (distance, path) or (inf, []) if no path or negative cycle."""
    INF = float('inf')
    dist = [INF] * n
    prev = [-1] * n
    dist[src] = 0

    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] != INF and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u

    # Check for negative cycles on the path to dst
    for u, v, w in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:
            return INF, []  # Negative cycle

    # Reconstruct path
    path = []
    node = dst
    while node != -1:
        path.append(node)
        node = prev[node]
    path.reverse()

    if path[0] != src:
        return INF, []  # No path exists

    return dist[dst], path
```


## Application: Currency Arbitrage Detection

Convert currency exchange rates to log space — a negative cycle in log-transformed weights means an arbitrage opportunity exists.


```
import math

def find_arbitrage(currencies: list[str], rates: list[list[float]]) -> bool:
    """
    Detect currency arbitrage: a sequence of conversions that returns
    more money than you started with.

    Transform: weight = -log(rate)
    Arbitrage exists ↔ negative cycle in transformed graph
    """
    n = len(currencies)
    edges = []

    for i in range(n):
        for j in range(n):
            if i != j and rates[i][j] > 0:
                # Negate log because Bellman-Ford finds minimum
                edges.append((i, j, -math.log(rates[i][j])))

    # Run Bellman-Ford from each source to catch all components
    for src in range(n):
        _, has_cycle = bellman_ford(n, edges, src)
        if has_cycle:
            return True  # Arbitrage opportunity detected

    return False
```


## SPFA (Shortest Path Faster Algorithm)

Queue-optimized Bellman-Ford — only re-relaxes nodes whose distance was just updated:


```
from collections import deque

def spfa(n: int, graph: list[list[tuple]], src: int) -> list[float]:
    """
    SPFA: Bellman-Ford with queue optimization.
    Average case much faster; worst case still O(V * E).
    """
    INF = float('inf')
    dist = [INF] * n
    dist[src] = 0
    in_queue = [False] * n
    in_queue[src] = True
    queue = deque([src])

    while queue:
        u = queue.popleft()
        in_queue[u] = False

        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                if not in_queue[v]:
                    in_queue[v] = True
                    queue.append(v)

    return dist
```


## LeetCode Problems

- LeetCode 743: Network Delay Time (Dijkstra or Bellman-Ford)

- LeetCode 787: Cheapest Flights Within K Stops (Bellman-Ford with K limit)

- LeetCode 1334: Find the City With Smallest Number of Neighbors at Threshold (Floyd-Warshall)

### K-Stop Constraint (LeetCode 787)


```
def find_cheapest_price(n: int, flights: list[list[int]],
                        src: int, dst: int, k: int) -> int:
    """
    Cheapest flight from src to dst with at most k stops (k+1 edges).
    Bellman-Ford limited to k+1 relaxation rounds.
    """
    INF = float('inf')
    dist = [INF] * n
    dist[src] = 0

    for _ in range(k + 1):  # At most k+1 edges = k stops
        temp = dist[:]  # Must copy to prevent using same-round updates
        for u, v, price in flights:
            if dist[u] != INF and dist[u] + price < temp[v]:
                temp[v] = dist[u] + price
        dist = temp

    return dist[dst] if dist[dst] != INF else -1
```


## Related Graph Topics
- [BFS vs DFS](https://www.techinterview.org/post/3233460119/bfs-vs-dfs-when-to-use-each-with-examples/) — Bellman-Ford is a relaxation algorithm, not a traversal; but understanding graph traversal is prerequisite for shortest path algorithms
- [Minimum Spanning Tree](https://www.techinterview.org/post/3233460138/minimum-spanning-tree-prims-and-kruskals-algorithms/) — MST minimizes total edge weight connecting all nodes; Bellman-Ford finds shortest path from one source; related but different objectives