Bellman-Ford / Shortest Path with Constraints

The Motivating Problem

Consider LeetCode 787. Cheapest Flights Within K Stops: you are given $n$ cities connected by flights, each with a price. Given a source city, a destination city, and an integer $K$, find the cheapest route from source to destination with at most $K$ stops. If no such route exists, return -1.

This looks like a shortest path problem, so your first instinct might be Dijkstra's algorithm. But there is a critical constraint: at most $K$ stops. This constraint changes everything.

Why Dijkstra Fails with Constraints

Dijkstra's algorithm works by greedily settling nodes in order of their shortest distance. Once a node is popped from the priority queue, its distance is considered final. The algorithm discards suboptimal paths because it assumes they can never lead to a better result.

But when you have a constraint like "at most $K$ stops," a suboptimal path might be the only one that satisfies the constraint. Suppose you have two paths from A to D: one costs 100 and uses 1 stop, another costs 50 but uses 4 stops. If $K = 2$, Dijkstra would settle D with cost 50 via the 4-stop path, then never reconsider the 1-stop path. But the 4-stop path violates the constraint, and the correct answer is 100.

The fundamental issue is that Dijkstra prunes paths based solely on cost, ignoring auxiliary constraints. It has no mechanism to keep multiple candidate paths to the same node that differ in how many edges they use.

Bellman-Ford: Relax All Edges Repeatedly

The Bellman-Ford algorithm takes a completely different approach. Instead of greedily settling nodes, it systematically relaxes all edges in rounds. In each round, it considers every edge and checks whether routing through that edge improves the shortest known distance to the destination node.

The key property is this: after $k$ rounds of relaxation, the distance array contains the shortest paths using at most $k$ edges. This is exactly the structure we need for the "at most $K$ stops" constraint.

The algorithm works as follows. Initialize a distance array with infinity for every node, except the source which gets distance 0. Then perform up to $V-1$ rounds. In each round, go through every edge $(u, v, w)$ and check if dist[u] + w < dist[v]. If so, update dist[v]. After $V-1$ rounds, you have the true shortest paths from the source to all reachable nodes.

Why $V-1$ rounds? A shortest path in a graph with $V$ nodes can have at most $V-1$ edges (visiting each node once). So $V-1$ rounds are sufficient to discover all shortest paths.

Walking Through an Example

Consider 4 cities (0, 1, 2, 3) with these flights: 0 to 1 costs 100, 0 to 2 costs 500, 1 to 2 costs 100, 2 to 3 costs 100. We want the cheapest flight from city 0 to city 3 with at most 1 stop ($K = 1$, meaning at most 2 edges).

Edges: (0,1,100), (0,2,500), (1,2,100), (2,3,100).

Start: dist = [0, inf, inf, inf].

Round 1 (paths using at most 1 edge): Examine each edge. Edge (0,1,100): dist[0] + 100 = 100 < inf, so dist[1] = 100. Edge (0,2,500): dist[0] + 500 = 500 < inf, so dist[2] = 500. Edge (1,2,100): dist[1] is still inf from the previous iteration's snapshot (we use the distances from the start of the round, not mid-round updates). Edge (2,3,100): dist[2] is still inf from the snapshot.

Wait. This is the crucial detail. For the constrained version, we must use a copy of the distance array from the previous round. If we update in place, an edge relaxed early in the round can affect edges relaxed later, effectively allowing more edges than intended.

Using a copy: After round 1, dist = [0, 100, 500, inf].

Round 2 (paths using at most 2 edges): Copy previous dist as prev = [0, 100, 500, inf]. Edge (0,1,100): prev[0] + 100 = 100, dist[1] already 100, no change. Edge (0,2,500): prev[0] + 500 = 500, dist[2] already 500, no change. Edge (1,2,100): prev[1] + 100 = 200 < 500, so dist[2] = 200. Edge (2,3,100): prev[2] + 100 = 600, so dist[3] = 600.

After round 2, dist = [0, 100, 200, 600].

Since $K = 1$ stop means at most 2 edges, we stop after round 2. The answer is dist[3] = 600, which corresponds to the path 0 -> 2 -> 3 costing 500 + 100 = 600.

Note that the path 0 -> 1 -> 2 -> 3 costs only 300, but it uses 3 edges (2 stops), which exceeds our $K = 1$ limit. If we ran a third round, dist[3] would drop to 300. The round-by-round structure of Bellman-Ford naturally enforces the edge count constraint.

Code: Cheapest Flights Within K Stops

For LeetCode 787, the constrained Bellman-Ford translates directly into clean code:

def findCheapestPrice(n, flights, src, dst, k):
    dist = [float('inf')] * n
    dist[src] = 0

    # k stops means at most k+1 edges
    for i in range(k + 1):
        prev = dist[:]  # snapshot of previous round
        for u, v, w in flights:
            if prev[u] + w < dist[v]:
                dist[v] = prev[u] + w

    return dist[dst] if dist[dst] < float('inf') else -1

The snapshot prev = dist[:] is essential. Without it, updates within a single round could chain together, effectively using more edges than the round number allows. By reading from the previous round's distances and writing to the current round's, we guarantee that round $i$ only considers paths with at most $i$ edges.

The time complexity is $O(K \cdot E)$ where $E$ is the number of flights and $K$ is the stop limit. Space is $O(V)$ for the distance arrays.

Negative Weight Edges

Beyond constrained shortest paths, Bellman-Ford has another major advantage over Dijkstra: it correctly handles negative edge weights.

Dijkstra's greedy approach fails with negative edges because settling a node early does not guarantee optimality: a later path through a negative edge could yield a lower total cost. Bellman-Ford has no such issue. It considers all edges in every round, so negative edges are naturally incorporated.

After the standard $V-1$ rounds, Bellman-Ford has found the shortest paths in any graph without negative cycles. But what if a negative cycle exists, a cycle whose edge weights sum to a negative number? In that case, you can keep going around the cycle to reduce the path cost indefinitely, meaning no finite shortest path exists for nodes reachable from the cycle.

To detect this, run one additional round (the $V$-th round). If any distance is still being improved, a negative cycle is reachable from the source. In $V-1$ rounds, all shortest paths of at most $V-1$ edges are settled. If a $V$-th round finds an improvement, it means there is a shorter path with $V$ edges, which is only possible if it revisits a node, forming a cycle with negative total weight.

Code: General Bellman-Ford with Negative Cycle Detection

def bellman_ford(n, edges, source):
    dist = [float('inf')] * n
    dist[source] = 0

    # Relax all edges V-1 times
    for i in range(n - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] != float('inf') and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        if not updated:
            break  # early termination: no changes means we're done

    # Check for negative cycles with one more round
    for u, v, w in edges:
        if dist[u] != float('inf') and dist[u] + w < dist[v]:
            return None  # negative cycle detected

    return dist

Note two implementation details. First, the dist[u] != float('inf') check prevents relaxing edges from unreachable nodes, which could cause incorrect behavior with negative edges. Second, the early termination optimization: if no distance is updated in a round, all subsequent rounds will also produce no updates, so we can stop early.

Unlike the constrained version, the general Bellman-Ford does not need the snapshot copy. In-place updates are fine here because we are not restricting the number of edges. In fact, in-place updates can make the algorithm converge faster since improvements propagate within the same round.

SPFA: A Practical Optimization

The Shortest Path Faster Algorithm (SPFA) is a queue-based optimization of Bellman-Ford. The observation is that most edge relaxations in a round are wasted: if dist[u] has not changed since the last round, re-examining edges from $u$ will not produce any improvements.

SPFA maintains a queue of nodes whose distances have recently been updated. Only edges from these nodes are examined. A node is enqueued when its distance improves, and dequeued when its edges are processed. A boolean array tracks which nodes are currently in the queue to avoid duplicates.

from collections import deque

def spfa(n, graph, source):
    dist = [float('inf')] * n
    dist[source] = 0
    in_queue = [False] * n
    in_queue[source] = True
    queue = deque([source])

    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]:
                    queue.append(v)
                    in_queue[v] = True

    return dist

SPFA's worst-case time complexity is the same as Bellman-Ford: $O(VE)$. In practice, it often runs much faster, empirically close to $O(E)$ on random graphs. However, adversarial inputs can force worst-case behavior. For competitive programming, SPFA is popular for its simplicity and speed on typical inputs, but be aware that some problem setters deliberately construct anti-SPFA test cases.

To detect negative cycles with SPFA, count how many times each node is enqueued. If any node is enqueued $V$ or more times, a negative cycle exists.

When to Use Bellman-Ford

Use Bellman-Ford (or its constrained variant) in these situations:

The graph has negative edge weights. Dijkstra cannot handle these, but Bellman-Ford can.

You need to detect negative cycles. The $V$-th relaxation check is the standard approach.

You need shortest paths with a constraint on the number of edges. The round-by-round structure directly models "at most $k$ edges." This is the pattern behind LeetCode 787. Cheapest Flights Within K Stops.

Related problems include LeetCode 743. Network Delay Time (solvable with either Dijkstra or Bellman-Ford) and LeetCode 505. The Maze II (weighted shortest path).

Complexity Analysis

Bellman-Ford runs $V-1$ rounds, each examining all $E$ edges, giving $O(VE)$ time complexity. With early termination, the best case is $O(E)$ (one round with no updates). Space complexity is $O(V)$ for the distance array, plus $O(E)$ to store the edge list.

Compared to Dijkstra's $O((V + E) \log V)$ with a binary heap, Bellman-Ford is slower for graphs with non-negative weights. But it is simpler to implement (no priority queue needed), handles negative weights, detects negative cycles, and naturally supports edge-count constraints. When any of these properties are needed, Bellman-Ford is the right tool.

Recognizing this pattern

You're probably looking at Bellman-Ford when:

• The shortest-path graph can have negative edge weights, so Dijkstra is unsafe
• The problem caps the path at most K edges, K stops, or K layovers between source and destination
• You must detect a negative cycle, an arbitrage opportunity, or an ever-decreasing loop
• The relaxation needs to happen in rounds rather than greedily, because each round corresponds to one more edge in the path

Common templates:

• Round-by-round edge relaxation: for K rounds, copy the distances and relax every edge using the previous round's snapshot. Example: Cheapest Flights Within K Stops.
• Negative cycle detection: run V-1 rounds, then check if any edge still relaxes on the Vth round. Example: Currency Exchange (arbitrage).
• SPFA queue-based variant: keep a queue of nodes whose distance just dropped and relax only their outgoing edges. Example: Network Delay Time.
• Edge-list shortest path: when the graph is given as an unordered list of $(u, v, w)$ edges, Bellman-Ford avoids building an adjacency list. Example: Cheapest Flights Within K Stops.