Distances between all pairs of vertices
Dijkstra's algorithm and Bellman-Ford both find the distances from one source. Some problems ask for the distance between many different pairs of vertices:
There are cities and two-way roads with lengths. Answer queries, each asking for the length of the shortest route between two cities, or -1 if there is none.
The first line has , and . Then come the roads as , and , and the queries as and .
Constraints
Sample · Input
4 3 5 1 2 5 1 3 9 2 3 3 1 2 2 1 1 3 1 4 3 2
Output
5 5 8 -1 3
In the sample the shortest route from city 1 to city 3 goes through city 2 and has length , less than the direct road of length 9. No road leads to city 4, so the fourth query is answered with .
There can be queries and only 500 cities, so it pays to compute the distance between every pair of cities once, keep the distances in a table, and answer each query by looking it up. We could fill the table by running Dijkstra's algorithm from each city in turn. The Floyd-Warshall algorithm is shorter to write, three nested loops and no heap, and unlike Dijkstra's algorithm it also works when some weights are negative, as long as no cycle has weights that add up to less than 0.
One more middle vertex in each round
The algorithm keeps a table d with a row and a column for every vertex. At the start d[i][j] is the weight of the edge , or if there is no such edge, and d[i][i] is 0. These are the lengths of the shortest paths that pass through no other vertex on the way. We watch the table on the courier map of this lesson, where it starts like this:
| From | to 0 | to 1 | to 2 | to 3 | to 4 |
|---|---|---|---|---|---|
| 0 | 0 | 4 | 1 | ∞ | ∞ |
| 1 | ∞ | 0 | ∞ | 1 | ∞ |
| 2 | ∞ | 2 | 0 | 5 | ∞ |
| 3 | ∞ | ∞ | ∞ | 0 | ∞ |
| 4 | ∞ | ∞ | ∞ | ∞ | 0 |
Bellman-Ford limits the number of edges a path may have and raises the limit by one in each round. Floyd-Warshall limits instead which vertices a path may pass through on the way. The vertices of a path other than its first and its last are its middle vertices: the path 0 → 2 → 1 → 3 has the middle vertices 2 and 1. The algorithm works in rounds, one for each vertex , and round allows as a middle vertex. For every pair , it checks whether going from to and then from to is shorter than the best path from to found so far:
Round 0 changes nothing on the courier map, because no road leads into town 0. Round 1 tries town 1 in the middle. Town 3 is 1 minute from town 1, so every town with a path to town 1 gets a path to town 3: town 0 in minutes, and town 2 in , which beats its direct road of 5.
| From | to 0 | to 1 | to 2 | to 3 | to 4 |
|---|---|---|---|---|---|
| 0 | 0 | 4 | 1 | 5 | ∞ |
| 1 | ∞ | 0 | ∞ | 1 | ∞ |
| 2 | ∞ | 2 | 0 | 3 | ∞ |
| 3 | ∞ | ∞ | ∞ | 0 | ∞ |
| 4 | ∞ | ∞ | ∞ | ∞ | 0 |
Round 2 tries town 2 in the middle. From town 0, the way through town 2 reaches town 1 in minutes and town 3 in . The second of these uses the entry d[2][3], which round 1 has just lowered to 3. That entry stands for the path 2 → 1 → 3, so the new path from town 0 to town 3 is 0 → 2 → 1 → 3. It has two towns in the middle, although round 2 looked only at town 2.
| From | to 0 | to 1 | to 2 | to 3 | to 4 |
|---|---|---|---|---|---|
| 0 | 0 | 3 | 1 | 4 | ∞ |
| 1 | ∞ | 0 | ∞ | 1 | ∞ |
| 2 | ∞ | 2 | 0 | 3 | ∞ |
| 3 | ∞ | ∞ | ∞ | 0 | ∞ |
| 4 | ∞ | ∞ | ∞ | ∞ | 0 |
Rounds 3 and 4 change nothing, since no road leaves town 3 and none touches town 4. The top row of the table now holds the distances from town 0 that the other pages of this lesson computed, 0, 3, 1, 4 and , and each other row holds the distances from its own town.
What the table holds after each round
After round , d[i][j] is the length of the shortest path from to whose middle vertices all come from 0 to .
Suppose this is true before round , for paths whose middle vertices are all below . A shortest path from to that may also use either avoids , and then d[i][j] already holds its length, or passes through , and then only once, since a shortest path does not need to visit a vertex twice.
In the second case the path splits into a part from to and a part from to . Each part has only vertices below in the middle, and each is as short as such a path can be, because a shorter one could take its place and shorten the whole path. So their lengths are d[i][k] and d[k][j]. Round takes the smaller of the two cases.
So the statement is true after round as well. After the last round every vertex is allowed in the middle, and the table holds the true distances.
The argument needs to be the outermost loop. If is the innermost loop, the entry d[i][j] gets all its tries in one pass over and is never looked at again, and during that pass many of the entries it reads still hold single edges. Take the one-way roads 0 → 1, 1 → 3, 3 → 2 and 2 → 0, each of weight 1. With innermost, d[0][2] is left at , although the path 0 → 1 → 3 → 2 has length 3.
The table is updated in place, while Cheapest Flights needed a copy. No copy is needed here, because round reads only row and column of the table and does not change them: d[i][k] could only become d[i][k] + d[k][k], and d[k][k] is 0.
Negative weights are allowed as long as the graph has no negative cycle. If it has one, some d[i][i] ends up below 0, and that is how the algorithm shows it. On the courier map with the negative cycle 4 → 1 → 3 → 4, the entries d[1][1], d[3][3] and d[4][4] come out negative.
Floyd-Warshall in code
The program for Shortest Routes II reads the roads into the table, runs the three loops and answers the queries. A road can be used in both directions, so it sets two entries.
def main():
data = list(map(int, sys.stdin.buffer.read().split()))
n, m, q = data[0], data[1], data[2]
INF = float("inf")
d = [[INF] * (n + 1) for _ in range(n + 1)]
for v in range(1, n + 1):
d[v][v] = 0
pos = 3
for _ in range(m):
a, b, c = data[pos], data[pos + 1], data[pos + 2]
pos += 3
d[a][b] = min(d[a][b], c) # two roads may join the same pair
d[b][a] = min(d[b][a], c)
for k in range(1, n + 1): # the middle city, in the outermost loop
for i in range(1, n + 1):
for j in range(1, n + 1):
if d[i][k] + d[k][j] < d[i][j]:
d[i][j] = d[i][k] + d[k][j]
out = []
for _ in range(q):
a, b = data[pos], data[pos + 1]
pos += 2
out.append(-1 if d[a][b] == INF else d[a][b])
print("\n".join(map(str, out)))
main()On the sample input the program prints 5, 5, 8, -1 and 3.
Two roads can join the same pair of cities, so a road replaces an entry only when it is shorter. A query whose entry is still is answered with .
For the largest input the innermost line runs times. On our laptop this program needed between 4.5 and 7.5 seconds for that, depending on the Python version, and the limit on CSES is 1 second, so it is correct but too slow for the largest tests there. The C++ version of the same loops took about 0.05 seconds.
Step through the rounds
The widget shows the table after each round, which it calls a pass. It opens on the courier map, so the three tables above can be checked against it, and its second example is the sample of Shortest Routes II with the cities numbered from 0. The third example is the one-way cycle. With the loop order switched to k innermost, it leaves d[0][2] at .
Cost of Floyd-Warshall
- Filling the table
time - rounds over all pairs: steps for Shortest Routes II.
- Each query
time - One lookup in the finished table.
- Memory
- The table, entries.
The cube limits the algorithm to small graphs. With 3,000 vertices it would take steps.
Which method for which weights
The methods of this lesson and breadth-first search differ in the weights they accept and in what they cost. The table lists them from the most restricted to the most general, for a graph with vertices and edges.
| Weights | Method | Time | Used in this lesson for |
|---|---|---|---|
| All equal | BFS | no problem; see the BFS lesson | |
| 0 or 1 | 0-1 BFS | Minimum Obstacle Removal | |
| 0 or more | Dijkstra's algorithm with a heap | Network Delay Time, Path With Minimum Effort, Flight Discount, Investigation | |
| Any, negative cycles included | Bellman-Ford | High Score | |
| Any, with at most edges on a path | Bellman-Ford with a copy, rounds | Cheapest Flights Within K Stops | |
| Any without a negative cycle, between all pairs of a few hundred vertices | Floyd-Warshall | Shortest Routes II |
The limits of a problem narrow the choice. With vertices only BFS, 0-1 BFS and Dijkstra's algorithm are fast enough. When a weight can be negative, Dijkstra's algorithm is out, and the graph has to be small enough for Bellman-Ford or Floyd-Warshall.
Common mistakes with Floyd-Warshall
Putting the loop over the middle vertex inside the other two.
- Where it breaks
- With the one-way roads
0 → 1,1 → 3,3 → 2and2 → 0, each of weight 1, the loop order , , leavesd[0][2]at . The path0 → 1 → 3 → 2has length 3. - The fix
- The middle vertex goes in the outermost loop.
Overwriting an entry with every road that is read.
- Where it breaks
- If a road of length 3 between cities 1 and 2 is followed by another road of length 5 between the same cities, the table keeps 5, and the query
1 2prints 5 where the answer is 3. - The fix
- Keep the shorter road:
d[a][b] = min(d[a][b], c).
In C++, using the largest
long longas infinity.- Where it breaks
- A sum such as 5 plus the largest
long longoverflows to a negative number, which then looks like a very short path. On the sample the query1 4prints about where the answer is -1. - The fix
- Use an infinity that can be added to itself, such as .
Recall A graph has 300 vertices and 20,000 edges, one of them of weight −2. It has no negative cycle, and there are $10^5$ distance queries between arbitrary pairs. Which method fits?
Floyd-Warshall. The negative edge rules out Dijkstra's algorithm, and one run of Bellman-Ford for each of the 300 sources would cost up to relaxations. Floyd-Warshall accepts negative edges when there is no negative cycle, needs steps once, and then answers each query with one lookup.