C++UCS301
Graphs & ApplicationsC++17

Floyd–Warshall

Floyd–Warshall computes all-pairs shortest paths by progressively allowing each vertex as an intermediate.

What to understand

  • Dynamic programming state
  • Intermediate-vertex recurrence
  • Negative edges
  • Negative-cycle detection

Remember this

  1. 1Three nested loops give O(V³)
  2. 2Supports negative edges but not negative cycles
  3. 3dist[i][i] < 0 signals a negative cycle

Detailed notes

Floyd–Warshall defines dist_k(i,j) as the best path whose intermediate vertices come only from the first k vertices. A best path either avoids vertex k or splits into i→k and k→j paths that use earlier intermediates.

The algorithm supports negative edges because it does not greedily finalise distances. After completion, a negative diagonal entry indicates a reachable negative cycle affecting shortest-path meaning.

How it works

  1. 1Initialise diagonal zero, edges to weights, and missing edges to infinity.
  2. 2Place the intermediate-vertex loop outermost.
  3. 3Combine only finite subpaths.
  4. 4Optionally maintain a next matrix to reconstruct routes.

Worked trace

Allow one intermediate

A→B=5, B→C=2, A→C=10
  1. 1Before allowing B, best A→C is direct cost 10.
  2. 2Consider route A→B→C.
  3. 3Its cost is 5+2=7.
  4. 4Replace dist[A][C] with min(10,7).
Result: After B is allowed, dist[A][C]=7

Where it is used

  • All-pairs routing on small dense graphs
  • Transitive closure variants
  • Detecting negative cycles and computing network diameter

Common mistakes

  • Putting the via loop inside and breaking the DP stage invariant
  • Overflowing infinity plus a weight
  • Using O(V³) on graphs too large for cubic work

Complexity analysis

OperationBestAverageWorstExtra space
All-pairs shortest pathsO(V³)O(V³)O(V³)O(V²)

C++ implementation

C++17 reference
main.cpp

Floyd–Warshall dynamic programming

Guarding INF prevents overflow when one half of a candidate route does not exist.

for (int via = 0; via < vertices; ++via) {
    for (int from = 0; from < vertices; ++from) {
        for (int to = 0; to < vertices; ++to) {
            if (distance[from][via] == INF || distance[via][to] == INF)
                continue;
            distance[from][to] = min(
                distance[from][to],
                distance[from][via] + distance[via][to]
            );
        }
    }
}
12 linesUTF-8 · C++ study reference

Exam & viva

Open a prompt when you are ready to check your answer.