Pattern #60

All-pairs shortest paths, intermediate-node matrix DP, correct loop order, negative cycles, path reconstruction, closure variants, and Go templates.

Must Solve

10 core questions — solve these first.

1. 1.Floyd-Warshall All-Pairs Shortest Path
   Matrix DP with k as outer loopmedium
2. 2.Find the City With the Smallest Number of Neighbors
   Count threshold-reachable nodes after preprocessingmedium
3. 3.Shortest Distance Between Every Pair of Nodes
   Direct lookup after O(V³) workmedium
4. 4.Detect Negative Cycle Using Floyd-Warshall
   Check for a negative diagonalmedium
5. 5.Transitive Closure / Reachability
   Replace min-plus with boolean OR-ANDmedium
6. 6.Minimum Cost Between All Pairs
   Initialize direct edges and run matrix DPmedium
7. 7.Shortest Path in Weighted Matrix Graph
   Matrix input maps directly to distmedium
8. 8.All-Pairs Shortest Path with Negative Edges
   Works unless affected by a negative cyclehard
9. 9.Reconstruct Shortest Paths Between All Pairs
   Maintain next or predecessor matrixhard
10. 10.Find Minimum Cycle Cost — Related Variant
    Combine paths and closing edges carefullyhard

Also Important

8 closure and advanced variants.

1. 11.Evaluate Division — Closure Thinking
   Combine pair relations through intermediatesmedium
2. 12.Course Prerequisite Reachability
   Boolean transitive closuremedium
3. 13.Network Reachability Between Every Pair
   Precompute all reachability queriesmedium
4. 14.Minimum Distance Queries
   O(1) answer after preprocessingmedium
5. 15.Boolean Floyd-Warshall / Warshall Algorithm
   Reachability rather than distancemedium
6. 16.Minimax Path Variants
   Replace + with max and minimize resulthard
7. 17.Maximum Product / Probability Closure
   Change the algebra to maximize producthard
8. 18.Johnson's Algorithm — Advanced Comparison
   Better option for sparse all-pairs graphshard

How to Think

For every intermediate k:
  For every source i:
    For every target j:
      try route i → k → j

Go Quick Reference — Matrix DP

func floydWarshall(dist [][]int64) [][]int64 {
    n := len(dist)
    // Before calling: diagonal = 0 and missing edges = INF.
    for k := 0; k < n; k++ { // k MUST be outermost
        for i := 0; i < n; i++ {
            if dist[i][k] == INF { continue }
            for j := 0; j < n; j++ {
                if dist[k][j] == INF { continue }
                candidate := dist[i][k] + dist[k][j]
                if candidate < dist[i][j] {
                    dist[i][j] = candidate
                }
            }
        }
    }
    return dist
}

After processing k, dist[i][j] is the best path whose intermediate nodes come only from the processed set.

Variants & Path Reconstruction

Matrix [i][j] → best i-to-j cost
k → newly allowed middle node
Update → min(direct, i→k + k→j)
Loop order → k, i, j
Negative cycle → negative diagonal

Complexity

Time:          O(V³)
Distance space: O(V²)
Path matrix:    O(V²)
Query afterward: O(1)

Excellent for modest dense graphs or many pair queries; avoid it when V is huge and the graph is sparse.

Common Interview Mistakes

• Using the wrong loop order—k must be outermost

• Forgetting dist[i][i] = 0

• Adding INF values and overflowing

• Ignoring negative diagonal cycle detection

• Using O(V³) on an enormous sparse graph

• Overwriting a cheaper parallel edge

• Confusing all-pairs with one-source shortest path

Interview Rules

All pairs          → Floyd-Warshall
State              → dist[i][j]
Transition         → min(direct, through k)
Loop order         → k, then i, then j
Diagonal           → 0 initially
Negative cycle     → dist[v][v] < 0
Actual paths       → next matrix
Huge sparse graph  → repeated Dijkstra / Johnson

Floyd-Warshall → all pairs
State → dist[i][j]
Middle node → k
Loop order → k, i, j
Missing path → INF guard
Negative cycle → dist[v][v] < 0
Time → O(V³)

💡 Golden Rule: Let each node become an allowed intermediate, one at a time, and improve every source-target pair through it.