Floyd-Warshall all-pairs shortest paths in Python

Why it matters

Sometimes a program needs the distance between every pair of places, not only from one start. A delivery planner may want the travel time from each depot to each customer. A network engineer may want the latency between every pair of servers. Running Dijkstra's algorithm once from each vertex works when all weights are positive, but the code for it is longer, and it does not handle negative weights.

Floyd-Warshall is a short algorithm that fills in a full table of distances. It is three nested loops. It also handles negative weights, as long as there is no negative cycle. A negative cycle is a loop of edges whose total weight is below zero, so going around it again makes the route cheaper each time. The algorithm can detect this case.

This lesson covers the table, the three loops, the two cases with negative numbers, and the most common ways the code goes wrong. Single-source searches are covered in the earlier lesson on Dijkstra and Bellman-Ford.

The idea: allow one more stop

Start with the direct edges. A direct edge gives a route with no stops in between. For each vertex k in turn, the algorithm asks one question for every pair of vertices i and j: is the route from i to k followed by the route from k to j cheaper than the best route from i to j found so far? If yes, it keeps the cheaper one.

Consider the first round, where k is vertex 0. After this round, every pair's best route is either its direct edge or a route that goes through vertex 0 once. In the second round, k is vertex 1, so the routes may go through 0 or 1, or both. After the last round, every vertex has been allowed as a stop, so each pair's best route is the true best route.

Each round adds one new allowed stop. That is why the outer loop is over k, and why it must be the outermost loop.

Step 1: the table

The table is a list of lists named dist. The entry dist[i][j] holds the best known distance from vertex i to vertex j. The table is a matrix, which is a grid of numbers with rows and columns. Python has no built-in matrix type, so a list of rows is the usual choice.

Three rules set the starting table:

• The diagonal, where i equals j, is 0. A vertex is zero distance from itself.
• A direct edge from i to j puts its weight in dist[i][j].
• Every other cell is INF, which means "no known route yet".

In this lesson INF is math.inf. It is a float value that is larger than every number. Python integers have no largest value, so there is no overflow to guard against, as there is in a language with fixed-size integers. Two results follow from using math.inf:

• math.inf + 5 is math.inf, and min(math.inf, 5) is 5. A sum that uses an unreachable cell stays unreachable, so the loop does not need an extra check.
• min returns one of its inputs unchanged. The entries that hold whole numbers stay whole numbers, so the table prints 5, not 5.0.

The row is built with [[INF] * n for _ in range(n)]. The loop makes a new row for each value of _. Step 1 of the common mistakes shows what happens when the rows are not made separately.

Step 2: the triple loop

Here is the full program. It runs three examples. The first example uses four cities and only positive weights. The examples are the same as in the Java track, so the output can be compared with it.

Save the program as floyd_warshall.py and run it with python3 floyd_warshall.py. The output is:

Example 1: four cities, all weights positive
    0    3    5    6
    5    0    2    3
    3    6    0    1
    2    5    7    0
negative cycle: False
Example 2: one negative edge, no cycle
    0    2    5    4
  INF    0  INF    2
  INF   -3    0   -1
  INF  INF  INF    0
negative cycle: False
Example 3: cycle 1 -> 2 -> 1 has total weight -2
    0   -1   -2    0
  INF   -2   -3   -1
  INF   -3   -4   -2
  INF  INF  INF    0
negative cycle: True
vertex 1 is on a negative cycle
vertex 2 is on a negative cycle

The three loops are the whole algorithm. The loop over k is the outer one. Inside it, i and j range over all pairs. The line that does the work says: the route from i to k followed by the route from k to j costs dist[i][k] + dist[k][j]. Keep that route only if it is less than the current dist[i][j]. The function min does the comparison and keeps the smaller value.

Check one cell of Example 1 by hand. The cell dist[1][3] starts as INF, because there is no direct edge from city 1 to city 3. In round k = 0, the code computes dist[1][0] + dist[0][3], which is 8 + 7 = 15, so the cell becomes 15. In round k = 2, it computes dist[1][2] + dist[2][3], which is 2 + 1 = 3. Three is less than 15, so the cell becomes 3. The final table shows 3 in row 1, column 3. The route is 1, 2, 3.

A reader who knows Java will notice that the Java version of this code needs a long type and a check before each addition. In Python the math.inf value and unlimited integers remove the need for both.

Step 3: negative edges

Example 2 has an edge from city 2 to city 1 with weight -3. There is no negative cycle, so the table has finite answers wherever a route exists.

Check cell dist[0][1]. The direct edge from 0 to 1 costs 4. In round k = 2, the code computes dist[0][2] + dist[2][1], which is 5 + (-3) = 2. Two is less than 4, so the cell becomes 2. The route is 0, 2, 1.

Negative weights are the reason the sentinel needs care. With math.inf, the value math.inf - 3 is still math.inf, so an unreachable cell stays unreachable. If a program uses a large whole number as the sentinel instead, a cell with no route can drop below that number and look like a real route. The common mistakes section shows this case.

The cells that stay INF in Example 2 are the routes that do not exist. City 1 has only one edge, going to city 3, so it cannot reach city 0 or city 2. The table shows this.

Step 4: negative cycles

Example 3 has a loop: 1 to 2 with weight -1, then 2 back to 1 with weight -1. The total for going around once is -2. Each time the route goes around, it gets cheaper. No shortest route exists, because a route could always be made cheaper by going around one more time.

Floyd-Warshall cannot give a finite answer in that case. It does something useful instead. The diagonal starts at 0. If the algorithm later finds a route from i back to i with a total below 0, the diagonal cell drops below 0. That is the signal.

In Example 3, the diagonal entries for vertices 1 and 2 are -2 and -4 after the last round. These entries are negative, so has_negative_cycle returns True. The program also prints which diagonal entries are negative. In this small graph those vertices are exactly the vertices of the cycle. In general a negative diagonal entry means there is a route from that vertex back to itself with a negative total, which is enough to make the answers unreliable for that part of the graph.

The other values in that table are not trustworthy either. Look at dist[0][2], which is -2. The route 0, 1, 2 costs 1 - 1 = 0, and going around the loop lowers the cost again each time. No cheapest value exists, so -2 is only the value reached when the rounds stop. When there is a negative cycle, use the True or False answer, not the numbers.

The check must run after the last round. A cycle can use any vertex as a stop, so a negative value may appear only in a later round. Checking inside the loop can miss it.

Common mistakes

Step 1: building the rows with * n. A list times a number repeats the same list object. Here is a grid built the wrong way:

The output is:

[[0, 7, 0], [0, 7, 0], [0, 7, 0]]

Setting one cell changed the same cell in all three rows, because all three rows are one list. The fix is the list comprehension [[0] * 3 for _ in range(3)], which makes a new row each time.

Putting k in the wrong loop position. The code must loop over k first. The program below runs the same algorithm, but with i and j on the outside and k on the inside. It compares the two versions on random graphs and prints the first graph where they disagree. The random numbers depend on the random generator, so the trial number and the table below come from Python 3.14. Another version may print a different trial.

The output is:

trial 19
start:
[0, inf, 7, inf]
[inf, 0, inf, 3]
[3, 3, 0, inf]
[inf, inf, 8, 0]
correct:
[0, 10, 7, 13]
[14, 0, 11, 3]
[3, 3, 0, 6]
[11, 11, 8, 0]
wrong order:
[0, 10, 7, 13]
[inf, 0, 11, 3]
[3, 3, 0, 6]
[11, 11, 8, 0]

Compare row 1 in the two results. The correct version finds 14 from city 1 to city 0, through 3 and 2. The wrong version leaves it at inf. The loops reach cell (1, 0) before the cells it depends on have their final values, so the route 1, 3, 2, 0 is never found, and the table is wrong.

Using a large whole number as the sentinel. The program below uses 10**9 as "no route" and drops the check before each addition. It is Example 2 from Step 2.

The output is:

[0, 2, 5, 4]
[1000000000, 0, 1000000000, 2]
[999999997, -3, 0, -1]
[1000000000, 999999997, 1000000000, 0]

The cell dist[2][0] shows 999999997. No route goes from city 2 to city 0, so this number is fake. It is 10**9 - 3, which is less than the sentinel, so it looks like a route. The cell dist[3][1] has the same problem. The cells that show 1000000000 are still unreachable. Use math.inf, as this lesson does, or keep the check if dist[i][k] < BIG and dist[k][j] < BIG before each addition.

Using None as the sentinel. Some programs use None for "no route yet". Python does not allow arithmetic or comparisons with None, so the program stops with an error:

dist = [0, None, None]
candidate = dist[1] + 10

The output is:

Traceback (most recent call last):
  File "example.py", line 2, in <module>
    candidate = dist[1] + 10
                ~~~~~~~~^~~~
TypeError: unsupported operand type(s) for +: 'NoneType' and 'int'

The comparison dist[1] < 10 gives a different message, '<' not supported between instances of 'NoneType' and 'int'. The file name and line numbers depend on your file. The fix is to use math.inf as the sentinel.

Forgetting the zeros on the diagonal. If dist[i][i] stays inf, the table says that a city cannot reach itself. That is wrong, and it makes the table misleading even for positive weights. The program below leaves the diagonal out:

import math
INF = math.inf
n = 3
dist = [[INF] * n for _ in range(n)]
dist[0][1] = 4
for k in range(n):
    for i in range(n):
        for j in range(n):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
print(dist)

Its output is:

[[inf, 4, inf], [inf, inf, inf], [inf, inf, inf]]

Set the diagonal to 0 before the loops.

Checking for negative cycles too early. The negative-cycle check must run after the last round, because a cycle can use any vertex as a stop. A check inside the loop can report no cycle when one exists.

Using the algorithm on a very large graph. The three loops run n times n times n, which is n cubed. For 100 vertices that is 1,000,000 inner steps, which runs quickly. For 1,000 vertices it is 1,000,000,000 steps, which takes far too long in Python. For a single source on a large sparse graph, Dijkstra is the better choice.

An edge that names a city outside the range. The city numbers must be from 0 to n - 1. In the program below the edge (1, 3, 2) names city 3, but the graph has only three cities, numbered 0, 1 and 2.

import math
INF = math.inf
n = 3
dist = [[INF] * n for _ in range(n)]
for u, v, w in [(0, 1, 4), (1, 3, 2)]:
    dist[u][v] = min(dist[u][v], w)

The output is:

Traceback (most recent call last):
  File "example.py", line 6, in <module>
    dist[u][v] = min(dist[u][v], w)
                     ~~~~~~~^^^
IndexError: list index out of range

The message only says that an index was out of range. The edge (1, 3, 2) asks for index 3 of a list with 3 slots. The file name and line numbers depend on your file. The fix is to check the input data, because the data is wrong.

Practice

Try each exercise by hand first, then check with the program.

Exercise 1. How many times does the innermost line run for a graph with 5 vertices?

Show the answer

It runs 5 times 5 times 5, which is 125 times.

Exercise 2. The graph has three cities and two edges: 0 to 1 with weight 4, and 1 to 2 with weight 1. What is dist[0][2] after the algorithm finishes?

Show the answer

It is 5. Before any round, dist[0][2] is inf. In round k = 1, the code computes dist[0][1] + dist[1][2], which is 4 + 1 = 5. Five is less than inf, so the cell becomes 5.

Exercise 3. Why does the code use math.inf for "no route" and not a large whole number such as 10**9?

Show the answer

Adding a negative weight to math.inf gives math.inf, so an unreachable cell stays unreachable. Adding a negative weight to 10**9 gives a number just below 10**9, which looks like a route. Example 2 in the mistakes section shows the fake value 999999997.

Exercise 4. Predict the output of this program, then run it.

grid = [[0] * 2] * 2
grid[1][0] = 9
print(grid)

Show the answer

It prints [[9, 0], [9, 0]]. Both rows are the same list, so setting grid[1][0] also changed grid[0][0].

Exercise 5. Example 3 has the edge from 2 to 1 with weight -1. Remove that edge and keep the others. Does the graph still have a negative cycle?

Show the answer

No. The edges left are 0 to 1 with weight 1, 1 to 2 with weight -1, and 2 to 3 with weight 2. There is no loop in this graph, so no cycle can have a total below zero. The diagonal stays 0 for every vertex, and has_negative_cycle returns False.

Summary

• Floyd-Warshall fills a table of the cheapest route between every pair of vertices using three nested loops.
• The outer loop is over the allowed intermediate stop k, and it must be the outermost loop.
• Use math.inf for "no route", set the diagonal to 0, and build each row of the table separately.
• A negative value on the diagonal after the last round means a negative cycle exists, and the other numbers should not be trusted.
• The algorithm does about n cubed steps, so it suits small or dense graphs better than large sparse ones.