Skip to content
Tutorials Center
My learning

Topics

Lesson 136 of 225 ยท Shortest Paths and Spanning Trees

Floyd-Warshall Algorithm

Understand Floyd-Warshall all-pairs shortest paths: the DP idea, three nested loops, path reconstruction, negative cycles, transitive closure and city problems.

Most shortest-path algorithms answer one question: how far is everything from this start vertex? Sometimes you need all of it at once: a table with the distance between every pair of vertices. A route planner that precomputes distances between all depots, a tool that finds the "center" of a network, a compiler asking which module can eventually reach which other module. These are all-pairs shortest path problems.

You could run Dijkstra from every vertex, or Bellman-Ford if there are negative edges. Floyd-Warshall takes a different route. It is a short piece of dynamic programming: three nested loops over a V by V matrix, no heap, no queue, and it handles negative edges. It is slower for huge sparse graphs, but for graphs of a few hundred vertices it is hard to beat for simplicity.

The idea: allow one more stopover at a time

Number the vertices 0 to V - 1. Define

TEXT
d(k, i, j) = length of the shortest path from i to j that may only use
             vertices 0 .. k-1 as intermediate stops

With k = 0 no stops are allowed, so d(0, i, j) is just the direct edge weight (or infinity if there is none, and 0 when i == j). Now think about adding vertex k as a permitted stop. The best path from i to j either

  1. does not go through k: its length is d(k, i, j) as before, or
  2. goes through k exactly once (a shortest path never needs to visit a vertex twice): i to k, then k to j, both using only stops below k.
TEXT
d(k+1, i, j) = min( d(k, i, j),  d(k, i, k) + d(k, k, j) )

        direct or old route
   i ----------------------------> j
    \                             ^
     \  d(k,i,k)        d(k,k,j) /
      +--------->  k  ----------+

After k reaches V, any vertex may be a stop, so d(V, i, j) is the true shortest distance. The table looks 3-dimensional, but layer k+1 only reads layer k, and in layer k the row and column of k itself never change (d(k, k, j) cannot be improved by going through k). So we can update one matrix in place.

The algorithm in code

Python Floyd-Warshall on a small directed graph

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Row i, column j of the output is the shortest distance from i to j. Entries that stay inf mean "no path". Notice that the matrix is not symmetric, because the graph is directed.

Watch out: the loop over k must be the outermost one. It is natural to write i, j, k, but then the DP meaning is lost: when you process pair (i, j) the rows for later stopovers have not been updated yet. The code looks almost identical and gives wrong answers on some graphs, which is a nasty bug to find. The next example proves it.

Tracing it: the matrix after each stopover

Printing the matrix after every value of k shows the idea at work. Each round, the distances can only go down.

Python Watching the matrix improve for each k

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For instance, 0 to 3 starts at infinity (there is no edge). Allowing vertex 1 as a stop gives 0 โ†’ 1 โ†’ 3 with cost 12. Allowing vertex 2 then finds 0 โ†’ 1 โ†’ 2 โ†’ 3 with cost 9, since 4 + 3 + 2 is cheaper than 4 + 8. Each new stop can combine paths found earlier, which is the power of the DP.

Proving the loop order matters

Python Wrong loop order gives wrong answers

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The correct order finds the 3-edge route 0 โ†’ 3 โ†’ 2 โ†’ 1 (cost 3). The wrong order handles the pair (0, 1) before the distance from 0 to 2 is known, and row 0 is never revisited, so it reports a wrong answer.

Reconstructing the paths

The distance table only gives lengths. To print the actual route, keep a second matrix nxt[i][j] = "the first step to take when going from i to j". Initially it is j when an edge exists. Whenever going through k improves (i, j), the first step toward j becomes the first step toward k: nxt[i][j] = nxt[i][k].

Python Floyd-Warshall with path reconstruction

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Following nxt one hop at a time rebuilds the route in O(length). The whole structure costs one more V by V matrix.

Negative edges and negative cycles

Floyd-Warshall is fine with negative edge weights. A negative cycle shows up on the diagonal: if a vertex can reach itself with a total cost below 0, then dist[i][i] < 0 after the algorithm. Any pair whose route can pass through such a vertex has no well-defined shortest distance.

Python Negative weights and negative cycle detection

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Once a negative cycle exists, the numbers in the matrix can become huge negatives, and they are not meaningful. Check the diagonal first.

Transitive closure: who can reach whom?

If you only care about reachability, replace numbers by booleans and min/+ by or/and. This is Warshall's algorithm: reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j]). The transitive closure is the finished table. A neat trick is to store each row as an integer bitmask, so that one |= merges V bits at once, which makes the loops far cheaper than the plain version.

Python Transitive closure with and without bitmasks

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Using the matrix: the city with the fewest neighbors

A classic problem: given roads between cities and a distance threshold, find the city that can reach the fewest other cities within the threshold (ties go to the largest index). Running Floyd-Warshall once gives all distances, and then it is just counting.

Python Fewest reachable cities within a threshold

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Complexity

There are three loops of V iterations each, so the time is O(Vยณ) regardless of how many edges there are. The matrix needs O(Vยฒ) memory (twice that if you keep nxt). Compare with running a single-source algorithm from every vertex:

Approach Time Best when
Floyd-Warshall O(Vยณ) dense graph, V up to a few hundred, negative edges allowed
Dijkstra from every vertex O(V ยท (V + E) log V) sparse graph, non-negative weights
Bellman-Ford from every vertex O(Vยฒ ยท E) rarely; Johnson's trick is better (see variants)

For V = 400 the triple loop is 64 million simple steps, a few seconds in plain Python, so for larger inputs use NumPy-style vectorization or switch algorithms. Most interview and contest constraints that allow Floyd-Warshall say V is at most about 400 to 500.

Common mistakes

  • Wrong loop order. k must be outermost.
  • Using a huge integer as infinity and then adding two of them. In other languages INF + INF overflows; use INF = 10**9 with care, or check before adding. Python's float("inf") is safe.
  • Forgetting dist[i][i] = 0. Then a vertex looks unreachable from itself.
  • Overwriting parallel edges. If the input can list two edges between the same pair, keep the minimum.
  • Reading results after a negative cycle without checking the diagonal.

When to use it

Choose Floyd-Warshall when you need many or all pairwise distances, the graph is small or dense, you want code that is short and easy to get right, or you need transitive closure. For one start vertex use Dijkstra or Bellman-Ford. The same "allow one more intermediate item" idea reappears in dynamic programming on sequences.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does d(k, i, j) mean in Floyd-Warshall?

    Each round allows one more vertex as a possible stopover; after all V vertices are allowed, the table holds the true shortest distances.
  2. 2. Which loop must be outermost?

    The DP builds on all pairs having been updated for stopovers 0..k-1 before stopover k is added, so k has to be the outer loop.
  3. 3. What is the time and space complexity?

    Three nested loops over V give V^3 steps and the distance matrix has V^2 entries.
  4. 4. How do you detect a negative cycle after running the algorithm?

    A vertex that can return to itself at negative cost ends up with dist[i][i] below zero.
  5. 5. In Warshall's transitive closure, which operation replaces min and +?

    reach[i][j] becomes reach[i][j] or (reach[i][k] and reach[k][j]): i reaches j directly, or by way of k.

Summary

  • Floyd-Warshall computes all-pairs shortest paths with three nested loops, k outermost.
  • DP idea: d(k+1, i, j) = min(d(k, i, j), d(k, i, k) + d(k, k, j)); update one matrix in place.
  • Time O(Vยณ), space O(Vยฒ); independent of the number of edges.
  • Works with negative edges; a negative value on the diagonal reveals a negative cycle.
  • A nxt matrix rebuilds actual paths; boolean version gives the transitive closure.
  • Best for small or dense graphs; prefer Dijkstra per vertex for big sparse graphs.

Next: 0-1 BFS, A* and Other Shortest Paths