liveBook · Manning

Floyd–Warshall

As explained in Algorithms Every Programmer Should Know

The Floyd-Warshall algorithm is a dynamic programming algorithm that computes shortest-path distances between every pair of vertices in a weighted graph.

Suppose a network needs the shortest distance between every pair of nodes, not just routes from one starting point. Floyd–Warshall solves this all-pairs shortest-path problem with dynamic programming. It builds a distance table once, then lets each pair’s answer be looked up directly. That differs from Dijkstra’s single-source approach, which would need to run again for each starting node. section 9.0 section 9.4

Start with a square matrix: each row is a starting node and each column is a destination. Then test possible detours.

  • Put 0 on the diagonal, each direct edge’s weight in its cell, and infinity where no direct edge exists. section 9.1
  • Choose a node k as a possible bridge. For every start i and destination j, keep the cheaper of the current distance and the route through k: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). section 9.1
  • Repeat with every node as k. The bridge loop must surround the start and destination loops; the matrix can be updated in place. section 9.1 section 9.4

A shortcut appears

Imagine the current distance from node 4 to node 2 is infinity: no direct route is recorded. When node 1 becomes the bridge, the algorithm finds a route costing 2 + 2 = 4 and replaces infinity with 4. In the next phase, using node 2 as a bridge reveals a route from node 1 to node 4 costing 2 + 3 = 5. A phase need not change anything: testing node 3 finds no new shortcut in this example. section 9.1

Figure 9.2 Phase one of the algorithm (k=1). Node 1 is tested as an intermediate bridge for every pair of nodes. The algorithm discovers that routing a path from Node 4 to Node 2 via Node 1 costs 4 (2 + 2 = 4). Since 4 is less than the previous cost of infinity, a shorter route is found, and the matrix is overwritten in place to form A1

The first bridge phase shows why an indirect route can turn an infinite matrix entry into a finite distance. section 9.1

Three nested loops take O(V³) time whether the graph has few edges or many. The distance matrix takes O(V²) space, but afterward a distance lookup takes O(1) time. This trade-off suits dense graphs needing many pairwise answers; sparse graphs may be better served by repeated single-source searches. section 9.3 section 9.4

Negative edge weights are allowed, but a negative-weight cycle makes a shortest distance undefined: repeatedly circling it keeps lowering the cost. After the loops finish, check the diagonal. Any dist[i][i] below zero signals such a cycle. section 9.3

How Algorithms Every Programmer Should Know covers it

How deep it goes
Works through matrix initialization and successive bridge phases, then gives nested-loop pseudocode and a Python implementation.
Examples
Traces a four-node directed graph as successive bridge nodes reveal shorter routes in its distance matrix.
What it assumes
Assumes familiarity with weighted graph nodes and edges, while showing how to initialize the distance matrix from direct connections.
What you can do after
Build it from scratch to precompute pairwise distances and diagnose negative-weight cycles by checking the finished matrix’s diagonal.
How it connects
Connects dynamic programming and all-pairs shortest paths with Dijkstra’s algorithm, dense graphs, and negative-weight cycles.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.