Bellman–Ford and Floyd–Warshall Algorithms in Python

By Engr. Henry Akpan

Shortest Paths Beyond Dijkstra

Dijkstra's algorithm is the standard way to find shortest paths, but it has two limitations. It cannot handle edges with negative weights, which appear in problems involving refunds, energy gains or currency exchange, and it finds paths from only one starting point at a time. Two other classic algorithms fill these gaps. Bellman–Ford works with negative edges and detects negative cycles, and Floyd–Warshall finds the shortest paths between every pair of vertices at once. This tutorial covers both in Python: how they work, why Dijkstra fails with negative edges, path reconstruction, negative-cycle detection with a currency-arbitrage example, running times, and how to choose an algorithm. It builds on the tutorial on Dijkstra's algorithm.

Why Dijkstra Fails with Negative Edges

Dijkstra's algorithm finalises the closest unvisited vertex, assuming that no later path can ever be shorter. A negative edge breaks that assumption: a path that looks longer at first can become shorter when it later crosses a negative edge.

For example, suppose S → A costs 2, S → B costs 5, and B → A costs −4. Dijkstra finalises A at distance 2, but the true shortest path is S → B → A, costing 5 − 4 = 1.

A negative cycle, a loop whose total weight is negative, is even worse: going round it again and again makes the path cheaper without limit, so no shortest path exists at all.

Relaxation

All three algorithms are built on one operation, called relaxing an edge u → v of weight w: if going through u gives a shorter route to v, update v's distance.

if dist[u] + w < dist[v]: dist[v] = dist[u] + w

Dijkstra relaxes edges in a clever order using a heap. Bellman–Ford simply relaxes every edge, again and again.

The Bellman–Ford Algorithm

  1. Set the distance to the source to 0, and every other distance to infinity.
  2. Repeat V − 1 times: relax every edge.
  3. Check every edge once more. If any distance can still be reduced, the graph has a negative cycle reachable from the source.

Why V − 1 rounds? A shortest path with no cycles uses at most V − 1 edges. After round k, every shortest path of up to k edges has been found, so V − 1 rounds are always enough.

INF = float("inf")

def bellman_ford(vertices, edges, source):
    dist = {v: INF for v in vertices}
    prev = {v: None for v in vertices}
    dist[source] = 0
    for _ in range(len(vertices) - 1):
        changed = False
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u
                changed = True
        if not changed:
            break                      # nothing improved: finished early
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            raise ValueError("graph contains a negative cycle")
    return dist, prev

def path_to(prev, target):
    path = []
    while target is not None:
        path.append(target)
        target = prev[target]
    return path[::-1]

vertices = ["S", "A", "B", "C", "D"]
edges = [("S", "A", 2), ("S", "B", 5), ("B", "A", -4),
         ("A", "C", 3), ("B", "D", 6), ("C", "D", 1)]
dist, prev = bellman_ford(vertices, edges, "S")
print(dist)
print(" -> ".join(path_to(prev, "D")))

Output:

{'S': 0, 'A': 1, 'B': 5, 'C': 4, 'D': 5}
S -> B -> A -> C -> D

The best route to A goes through B and uses the negative edge, exactly the case that Dijkstra gets wrong. The prev dictionary records how each vertex was reached, so the full path can be rebuilt by walking backwards from the target.

Running time: O(V × E), since each round checks all E edges. That is slower than Dijkstra's O(E log V), so use Bellman–Ford only when negative edges are possible.

Detecting a Negative Cycle: Currency Arbitrage

Suppose a sequence of currency exchanges, starting and ending with the same currency, turns 1 unit into more than 1 unit. That is an arbitrage opportunity. Exchange rates multiply, but taking logarithms turns products into sums: a cycle of rates whose product is greater than 1 has a sum of logarithms greater than 0. So if each edge weight is set to −log(rate), an arbitrage cycle becomes a negative cycle, which Bellman–Ford can detect.

import math

rates = {                          # made-up exchange rates for illustration
    ("NGN", "USD"): 1 / 1500,
    ("USD", "EUR"): 0.92,
    ("EUR", "NGN"): 1650,
    ("USD", "NGN"): 1490,
    ("EUR", "USD"): 1.08,
}
currencies = ["NGN", "USD", "EUR"]
log_edges = [(a, b, -math.log(r)) for (a, b), r in rates.items()]

try:
    bellman_ford(currencies, log_edges, "NGN")
    print("no arbitrage")
except ValueError as e:
    print("arbitrage possible:", e)

cycle = (1 / 1500) * 0.92 * 1650     # NGN -> USD -> EUR -> NGN
print(round(cycle, 3))

Output:

arbitrage possible: graph contains a negative cycle
1.012

With these rates, converting naira to dollars, dollars to euros and euros back to naira gives back about 1.2% more than you started with. Real markets close such gaps within moments, and transaction fees often wipe them out, but the same technique is used to find them.

The Floyd–Warshall Algorithm: All Pairs

To find the shortest distance between every pair of vertices, Floyd–Warshall uses dynamic programming. It considers each vertex k in turn as a possible intermediate stop, and for every pair (i, j) it asks: "Is going from i to k and then from k to j shorter than the best route from i to j found so far?"

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

After all V vertices have been tried as intermediates, every distance is the true shortest distance.

def floyd_warshall(n, edges):
    dist = [[0 if i == j else INF for j in range(n)] for i in range(n)]
    nxt = [[j if i == j else None for j in range(n)] for i in range(n)]
    for u, v, w in edges:
        dist[u][v] = w
        nxt[u][v] = v
    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]
                    nxt[i][j] = nxt[i][k]
    return dist, nxt

def fw_path(nxt, i, j):
    if nxt[i][j] is None:
        return []
    path = [i]
    while i != j:
        i = nxt[i][j]
        path.append(i)
    return path

towns = ["Lagos", "Ibadan", "Ilorin", "Abuja"]
roads = [(0, 1, 130), (1, 0, 130), (1, 2, 160), (2, 1, 160),
         (2, 3, 500), (3, 2, 500), (0, 3, 760), (1, 3, 650)]
dist, nxt = floyd_warshall(len(towns), roads)
for i, row in enumerate(dist):
    print(f"{towns[i]:<7}", row)
print(" -> ".join(towns[t] for t in fw_path(nxt, 0, 3)))

Output:

Lagos   [0, 130, 290, 760]
Ibadan  [130, 0, 160, 650]
Ilorin  [290, 160, 0, 500]
Abuja   [790, 660, 500, 0]
Lagos -> Abuja

(The distances here are illustrative road lengths in kilometres, not official figures.)

The table gives the shortest distance from every town to every other. The nxt table records the first step of each shortest path, so any route can be rebuilt. Note that the distances are not symmetric: the direct roads Lagos → Abuja and Ibadan → Abuja are one-way in this example, so the return trips must go through Ilorin.

The :<7 in the f-string pads each name to 7 characters, so the rows line up.

Running time: three nested loops over V vertices give O(V³). Floyd–Warshall is excellent for dense graphs with up to a few hundred vertices, and it is very short to write. It also handles negative edges, and a negative value on the diagonal (dist[i][i] < 0) reveals a negative cycle.

Choosing a Shortest-Path Algorithm

  • Unweighted graph: breadth-first search, in O(V + E).
  • Non-negative weights, one source: Dijkstra with a heap, in O(E log V). This is the usual choice for road maps and networks.
  • Negative weights possible, one source: Bellman–Ford, in O(VE), which also detects negative cycles.
  • Every pair of vertices, in a small or dense graph: Floyd–Warshall, in O(V³).
  • A directed acyclic graph: relax the edges in topological order, in O(V + E), even with negative weights.

Common Mistakes with Bellman–Ford and Floyd–Warshall

  • Using Dijkstra when negative edges exist, which gives wrong answers without any warning.
  • Running fewer than V − 1 rounds of Bellman–Ford, or skipping the final negative-cycle check.
  • Putting the k loop inside the i and j loops in Floyd–Warshall. The intermediate vertex k must be the outermost loop.
  • Treating undirected edges as one-way. For an undirected graph, add the edge in both directions.
  • Using a large number such as 999999 for infinity, which can overflow or create fake paths. Use float("inf").

Bellman–Ford and Floyd–Warshall: Practice Exercises

  1. Modify bellman_ford to return None instead of raising an error when a negative cycle exists.
  2. Use Floyd–Warshall to find the vertex whose greatest distance to any other vertex is smallest (the best place for a central depot) in the towns example.
  3. Check whether the cycle A → B → C → A with weights 1, −3 and 1 is a negative cycle using Bellman–Ford.

Sample solutions:

def safe_bellman_ford(vertices, edges, source):
    try:
        return bellman_ford(vertices, edges, source)[0]
    except ValueError:
        return None

def best_depot(names, dist):
    worst = [max(row) for row in dist]
    best = min(range(len(names)), key=lambda i: worst[i])
    return names[best], worst[best]

print(best_depot(towns, dist))
cycle_edges = [("A", "B", 1), ("B", "C", -3), ("C", "A", 1)]
print(safe_bellman_ford(["A", "B", "C"], cycle_edges, "A"))
print(safe_bellman_ford(["A", "B", "C"], [("A", "B", 1), ("B", "C", -3)], "A"))

Output:

('Ilorin', 500)
None
{'A': 0, 'B': 1, 'C': -2}

The cycle A → B → C → A has total weight 1 − 3 + 1 = −1, so it is a negative cycle. Without the edge back to A, the shortest distances are well defined.

Conclusion

Bellman–Ford relaxes every edge V − 1 times, finds single-source shortest paths even with negative edge weights in O(VE), and detects negative cycles with one extra pass. With weights of −log(rate), that detects arbitrage in currency exchange. Floyd–Warshall tries each vertex as an intermediate stop to find shortest paths between all pairs in O(V³), and a next-hop table rebuilds the routes. Use BFS for unweighted graphs, Dijkstra for non-negative weights, Bellman–Ford when weights can be negative, and Floyd–Warshall when you need every pair.

Related Tutorials