Shortest path algorithms that handle negative edge weights — the thing Dijkstra can't do. Bellman-Ford finds single-source shortest paths, Floyd-Warshall finds shortest paths between every pair of vertices.
AdvancedDijkstra's algorithm is fast — O(E log V) with a priority queue — but it has a blind spot. It uses a greedy strategy (always picking the closest unfinalized node), and that strategy assumes once a node is finalized, its distance won't improve. Negative edge weights break that assumption. A path through a negative edge can retroactively make a finalized node's distance shorter.
Picture a currency exchange. Converting USD → EUR → GBP → USD might actually give you more money than you started with. In graph terms, the exchange rates form edges, and that profitable loop is a negative cycle — a cycle whose total edge weight is negative. If you can loop forever and keep reducing the total cost, then "shortest path" is undefined (it's negative infinity). And Dijkstra has no way to detect this.
Bellman-Ford was developed by Richard Bellman (of dynamic programming fame) and Lester Ford Jr. in the late 1950s. It solves the single-source shortest path problem — finding the shortest distance from one starting node to every other node — and works with negative edge weights. The tradeoff is speed: O(V·E) instead of Dijkstra's O(E log V). But it can also detect negative cycles, which is genuinely useful.
The core idea is dead simple: relax (try to improve the distance estimate for) every edge, V-1 times. Each pass guarantees at least one more node gets its final shortest distance. If anything still changes on a V-th pass, there's a negative cycle — distances would keep decreasing forever.
Floyd-Warshall, named after Robert Floyd and Stephen Warshall (who independently worked on similar ideas in the early 1960s), takes a fundamentally different approach. Instead of finding shortest paths from one source, it computes shortest paths between every pair of vertices simultaneously. It runs in O(V³) time using dynamic programming — a technique where you solve a problem by breaking it into overlapping subproblems and caching results.
The DP question it asks at each step: "Can I get from vertex i to vertex j faster by routing through vertex k?" Three nested loops, one elegant recurrence. That's it.
Floyd-Warshall is the right tool when you need the full distance matrix (a V×V table of all pairwise shortest distances). Think network routing tables, transitive closure (determining which nodes can reach which other nodes), or checking if every node can reach every other node.
Bellman published his algorithm in 1958 as part of his work on dynamic programming at RAND Corporation. Ford's version came independently around the same time. The algorithm's simplicity — just a flat loop over all edges, repeated — made it easy to implement on the hardware of the era. Moore independently proposed a similar approach in 1957, which is why you sometimes see the name "Bellman-Ford-Moore."
Floyd-Warshall appeared in 1962. Floyd adapted Warshall's transitive closure algorithm (which determines reachability) to compute shortest paths. The key insight: by considering vertices as intermediate waypoints one at a time, you build up optimal paths incrementally.
Relaxation is just a fancy word for: "I found a shorter path, let me update." For each edge (u, v) with weight w:
If dist[u] + w < dist[v], set dist[v] = dist[u] + w.
Bellman-Ford does this for every edge, repeating V-1 times. Why V-1? Because the shortest path between any two vertices in a graph with V vertices uses at most V-1 edges (a path that visits every vertex exactly once). After pass k, you're guaranteed to have found all shortest paths that use at most k edges. So after V-1 passes, you've found them all.
Here's the step-by-step:
dist[u] + w < dist[v], update dist[v]Standard Bellman-Ford blindly relaxes every edge every pass, even edges that can't possibly help (because neither endpoint changed). The Shortest Path Faster Algorithm (SPFA) fixes this with a queue: only process vertices whose distances actually changed. In practice, SPFA is much faster. But adversarial inputs can still force O(V·E) worst case, so it's banned in some competitive programming judges.
Floyd-Warshall builds a V×V distance matrix, starting with just the direct edges. Then it systematically tries every possible "intermediate" vertex as a waypoint:
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
For each vertex k, it asks: "Is it shorter to go from i to j through k?" Three nested loops — k, i, j. That's where O(V³) comes from.
dist[i][j] = weight(i,j) if edge exists, ∞ otherwise, 0 on the diagonal (distance from any node to itself)dist[i][j] if routing through k is shorterdist[i][i] < 0, vertex i is part of a negative cycle (a path from i back to i with negative total weight)Watch Bellman-Ford relax edges round by round. The graph includes a negative edge to show how the algorithm handles them. Hit "Run Bellman-Ford" to see distance estimates converge, or "Detect Negative Cycle" to add a negative cycle and watch the algorithm catch it.
prev_dist = dist[:] at the start of each pass, and read from prev_dist while writing to dist.
dist[u] is ∞ and you compute dist[u] + w, in languages with real infinity (Python's float('inf')) this works fine — ∞ + w = ∞. But in languages with integer types, adding to MAX_VALUE causes overflow, producing a negative number that falsely triggers a relaxation. Always guard: if dist[u] != INF before relaxing.
| Algorithm | Time | Space | Negative Edges? | Detects Neg. Cycles? |
|---|---|---|---|---|
| Bellman-Ford | O(V·E) | O(V) | ✓ | ✓ |
| SPFA (optimized BF) | O(V·E) worst | O(V) | ✓ | ✓ |
| Floyd-Warshall | O(V³) | O(V²) | ✓ | ✓ |
| Dijkstra (comparison) | O(E log V) | O(V) | ✗ | ✗ |
Despite being slower in the general case, Bellman-Ford wins when:
def bellman_ford(edges, V, source):
"""Single-source shortest paths with negative edge support.
Args:
edges: list of (u, v, weight) tuples representing directed edges
V: number of vertices (labeled 0 to V-1)
source: starting vertex
Returns:
(distances, predecessors) — distances[i] is shortest distance from
source to vertex i, predecessors[i] is the previous vertex on that path.
Raises:
ValueError if a negative-weight cycle is reachable from source.
"""
# Initialize: source is 0, everything else is unreachable (infinity)
dist = [float('inf')] * V
prev = [-1] * V
dist[source] = 0
# Relax every edge V-1 times.
# Why V-1? A shortest path has at most V-1 edges (visits each vertex once).
# Each pass settles at least one more vertex's distance.
for i in range(V - 1):
updated = False
for u, v, w in edges:
# Guard: only relax from reachable vertices
if dist[u] != float('inf') and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
prev[v] = u
updated = True
# Early exit: if nothing changed this pass, we're done early
if not updated:
break
# V-th pass: if we can still relax any edge, a negative cycle exists
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
raise ValueError("Graph contains a negative-weight cycle")
return dist, prevdef bellman_ford_k_edges(edges, V, source, K):
"""Shortest paths using at most K edges.
Critical for "cheapest flight with at most K stops" problems.
The key difference: we copy dist[] before each pass to prevent
cascading updates within a single pass.
K stops = K+1 edges (you fly K+1 times to make K stops between).
"""
dist = [float('inf')] * V
dist[source] = 0
for _ in range(K):
# MUST copy before this pass — prevents cascading
prev_dist = dist[:]
for u, v, w in edges:
if prev_dist[u] != float('inf') and prev_dist[u] + w < dist[v]:
dist[v] = prev_dist[u] + w
return distfunction bellmanFord(edges, V, source) {
const dist = new Array(V).fill(Infinity);
const prev = new Array(V).fill(-1);
dist[source] = 0;
// V-1 relaxation passes
for (let i = 0; i < V - 1; i++) {
let updated = false;
for (const [u, v, w] of edges) {
if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
prev[v] = u;
updated = true;
}
}
if (!updated) break;
}
// Negative cycle detection pass
for (const [u, v, w] of edges) {
if (dist[u] !== Infinity && dist[u] + w < dist[v]) {
throw new Error("Negative-weight cycle detected");
}
}
return { dist, prev };
}def floyd_warshall(graph):
"""All-pairs shortest paths using dynamic programming.
Args:
graph: V×V adjacency matrix. graph[i][j] = weight of edge i→j.
Use float('inf') for no edge. Diagonal should be 0.
Returns: V×V distance matrix where dist[i][j] = shortest path from i to j.
The DP insight: dist_k[i][j] = shortest path from i to j using only
vertices 0..k as intermediates.
dist_k[i][j] = min(dist_{k-1}[i][j], dist_{k-1}[i][k] + dist_{k-1}[k][j])
We optimize space by updating in-place (safe because reading dist[i][k]
and dist[k][j] stays correct even after updates with intermediate k).
"""
V = len(graph)
dist = [row[:] for row in graph] # Deep copy — don't mutate input
# CRITICAL: k must be the outer loop. This is the DP ordering.
# k = "what intermediates are we allowed to use?"
for k in range(V):
for i in range(V):
for j in range(V):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
# Negative cycle check: any negative diagonal means a negative cycle
for i in range(V):
if dist[i][i] < 0:
raise ValueError(f"Negative cycle involving vertex {i}")
return distdef floyd_warshall_with_paths(graph):
"""Floyd-Warshall that also tracks the actual shortest paths.
next_hop[i][j] = the first vertex to go to on the shortest path from i to j.
To reconstruct path i→j: follow next_hop[i][j], then next_hop[next][j], etc.
"""
V = len(graph)
dist = [row[:] for row in graph]
# next_hop[i][j] = first step on shortest path from i to j
next_hop = [[None] * V for _ in range(V)]
for i in range(V):
for j in range(V):
if i != j and graph[i][j] != float('inf'):
next_hop[i][j] = j # Direct edge: go straight to j
for k in range(V):
for i in range(V):
for j in range(V):
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
next_hop[i][j] = next_hop[i][k] # Go toward k first
def get_path(i, j):
if next_hop[i][j] is None:
return [] # No path exists
path = [i]
while i != j:
i = next_hop[i][j]
path.append(i)
return path
return dist, get_pathBanks and trading firms use Bellman-Ford to detect arbitrage opportunities — sequences of currency exchanges that yield a profit. If you can convert USD → EUR → GBP → USD and end up with more dollars than you started, that's arbitrage. In graph terms, it's a negative cycle.
The trick: convert multiplication (exchange rates) into addition (which Bellman-Ford understands) by taking the negative logarithm. Multiplying exchange rates becomes summing negative logs. A profitable loop (product > 1) becomes a negative cycle (sum < 0).
import math
def detect_arbitrage(currencies, rates):
"""Detect currency arbitrage using Bellman-Ford.
currencies: list of currency codes, e.g. ["USD", "EUR", "GBP", "JPY"]
rates: 2D matrix where rates[i][j] = exchange rate from currency i to j
(1 unit of i buys rates[i][j] units of j)
Returns: (has_arbitrage, cycle) where cycle is the profitable loop if found.
Math: We want to detect if any cycle has product of rates > 1.
Taking -log: product > 1 → sum of -log(rates) < 0 → negative cycle.
"""
V = len(currencies)
# Build edge list with -log weights
edges = []
for i in range(V):
for j in range(V):
if i != j and rates[i][j] > 0:
# -log(rate): a profitable exchange becomes a negative edge
weight = -math.log(rates[i][j])
edges.append((i, j, weight))
# Run Bellman-Ford from vertex 0 (choice doesn't matter for cycle detection)
dist = [float('inf')] * V
prev = [-1] * V
dist[0] = 0
for _ in range(V - 1):
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
prev[v] = u
# V-th pass: find a vertex involved in a negative cycle
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
# Found a negative cycle — trace it back
cycle = []
node = v
for _ in range(V): # Walk back V steps to ensure we're in the cycle
node = prev[node]
# Now trace the cycle
start = node
cycle.append(currencies[start])
node = prev[start]
while node != start:
cycle.append(currencies[node])
node = prev[node]
cycle.append(currencies[start])
cycle.reverse()
return True, cycle
return False, []
# Example with real-ish exchange rates
currencies = ["USD", "EUR", "GBP", "JPY", "CHF"]
rates = [
# USD EUR GBP JPY CHF
[1.0, 0.92, 0.79, 149.50, 0.88], # USD
[1.09, 1.0, 0.86, 163.20, 0.96], # EUR
[1.27, 1.17, 1.0, 189.50, 1.12], # GBP
[0.0067,0.0061,0.0053,1.0, 0.0059], # JPY
[1.14, 1.05, 0.90, 170.10, 1.0], # CHF
]
found, cycle = detect_arbitrage(currencies, rates)
if found:
print(f"Arbitrage found: {' → '.join(cycle)}")
else:
print("No arbitrage opportunity")In practice, real arbitrage opportunities are tiny (fractions of a cent) and disappear in milliseconds. High-frequency trading firms run this detection continuously, competing to exploit opportunities before anyone else. The algorithm itself is simple — the engineering challenge is speed.
min(dist[i][j], dist[i][k] + dist[k][j]) with reachable[i][j] = reachable[i][j] OR (reachable[i][k] AND reachable[k][j]). Now you have a matrix telling you whether any path exists between each pair — that's the transitive closure. Useful for "can node i eventually reach node j?" problems.
Start with the tagged difficulty and work your way up.