Bellman-Ford and Floyd-Warshall in Brief
26 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Dijkstra is fast but cannot handle a negative edge, and it only starts from one node. Two simple algorithms fill the gaps. Both are short to write; the price is a higher running time.
When Dijkstra is not enough
A negative cycle is a loop of edges whose weights add up to less than zero. Going around it again and again makes a route cheaper without end, so no shortest path exists.
A negative weight can mean a refund or a discount along a route. A route can then get cheaper by going through more roads. Dijkstra's "settled means final" rule breaks, so a different method is needed.
Bellman-Ford: relax every edge, V - 1 times
A shortest path has at most V - 1 edges. So loop over all edges V - 1 times and relax each one. After pass k, every route that uses k edges or fewer is correct. Stop early when a pass changes nothing.
def bellman_ford(n, edges, start): dist = [float('inf')] * n dist[start] = 0 for _ in range(n - 1): changed = False for u, v, w in edges: if dist[u] + w < dist[v]: dist[v] = dist[u] + w changed = True if not changed: break return distExample 1 · Bellman-Ford with a negative edge
def bellman_ford(n, edges, start): dist = [float('inf')] * n dist[start] = 0 for _ in range(n - 1): changed = False for u, v, w in edges: if dist[u] + w < dist[v]: dist[v] = dist[u] + w changed = True if not changed: break return dist
edges = [(0, 1, 4), (0, 2, 5), (2, 1, -3), (1, 3, 2)]print(bellman_ford(4, edges, 0))[0, 2, 5, 4]
What this code does
- The route 0 → 2 → 1 costs 5 - 3 = 2, cheaper than the direct edge of 4. Dijkstra with settle-once would miss it.
- Time O(V * E), space O(V).
Example 2 · Why V - 1 passes can be needed
edges = [(1, 3, 2), (2, 1, -3), (0, 1, 4), (0, 2, 5)]dist = [0, float('inf'), float('inf'), float('inf')]passes = 0while True: changed = False for u, v, w in edges: if dist[u] + w < dist[v]: dist[v] = dist[u] + w changed = True if not changed: break passes += 1print(passes, dist)3 [0, 2, 5, 4]
What this code does
- The edges are in a bad order, so each pass fixes only one more node along the path 0 → 2 → 1 → 3.
- Three passes change something and the fourth changes nothing. That is V - 1 changing passes at most.
The time is O(V * E) and the space is O(V). It works on an edge list directly, with no adjacency list.
Detecting a negative cycle
Run one more pass after V - 1 passes. If any distance still gets smaller, a negative cycle can be reached from the start. In a graph without one, the answer is already final by then.
Example 3 · Detect a negative cycle
edges = [(0, 1, 1), (1, 2, -3), (2, 0, 1)]n = 3dist = [0] + [float('inf')] * (n - 1)for _ in range(n - 1): for u, v, w in edges: if dist[u] + w < dist[v]: dist[v] = dist[u] + whas_cycle = any(dist[u] + w < dist[v] for u, v, w in edges)print(has_cycle)True
What this code does
- The loop 0 → 1 → 2 → 0 costs 1 - 3 + 1 = -1. Every lap makes it cheaper.
- The check at the end is one extra pass. Any improvement there means a negative cycle.
Floyd-Warshall: every pair at once
Keep a matrix of distances between all pairs. For each possible middle node k, check whether going from i to j through k is cheaper. The loop over k must be the outermost loop.
def floyd_warshall(dist): n = len(dist) for k in range(n): for i in range(n): for j in range(n): if dist[i][k] + dist[k][j] < dist[i][j]: dist[i][j] = dist[i][k] + dist[k][j] return distExample 4 · Floyd-Warshall on a small graph
INF = float('inf')n = 4dist = [[INF] * n for _ in range(n)]for i in range(n): dist[i][i] = 0for u, v, w in [(0, 1, 3), (1, 2, -1), (2, 3, 2), (0, 3, 10)]: dist[u][v] = w
for k in range(n): for i in range(n): for j in range(n): if dist[i][k] + dist[k][j] < dist[i][j]: dist[i][j] = dist[i][k] + dist[k][j]
for row in dist: print(*[x if x != INF else '-' for x in row])0 3 2 4 - 0 -1 1 - - 0 2 - - - 0
What this code does
- The matrix starts with direct edges and 0 on the diagonal. A dash means no route.
- The best route from 0 to 3 is 0 → 1 → 2 → 3 with cost 3 + (-1) + 2 = 4, which beats the direct edge of 10.
Example 5 · Use the matrix: the cheapest round trip
INF = float('inf')n = 4dist = [[INF] * n for _ in range(n)]for i in range(n): dist[i][i] = 0for u, v, w in [(0, 1, 3), (1, 2, -1), (2, 3, 2), (0, 3, 10)]: dist[u][v] = w
dist[3][0] = 1for k in range(n): for i in range(n): for j in range(n): if dist[i][k] + dist[k][j] < dist[i][j]: dist[i][j] = dist[i][k] + dist[k][j]
best = min(dist[i][j] + dist[j][i] for i in range(n) for j in range(n) if i != j)print(best)5
What this code does
- After adding an edge 3 → 0 of cost 1, the cheapest loop is 0 → 1 → 2 → 3 → 0 = 5.
- Once the matrix is ready, any pair question is a lookup.
Three nested loops give O(V cubed) time and O(V squared) space. For V up to about 400 this is fine in Python.
Which one to use
Pick by the weights and by how many start nodes you need.
- Equal weights: BFS, O(V + E).
- Weights of zero or more, one start: Dijkstra, O((V + E) log V).
- Negative weights or a cycle check, one start: Bellman-Ford, O(V * E).
- All pairs on a small graph (V up to about 400): Floyd-Warshall, O(V cubed).
Next step
Check your understanding
11 quick questions