Skip to main content

Floyd-Warshall and DP Shortest Paths

What This Concept Is​

Floyd–Warshall computes all-pairs distances using allowed intermediate vertices. Initialize each diagonal to zero and every other cell unreachable, then incorporate each edge with a minimum update. This preserves negative self-loops and selects the cheapest parallel edge for distance computation. For each k, then each i,j, consider a route via k only if both subroutes are reachable.

Without negative cycles, the recurrence is D_k(i,j)=min(D_(k-1)(i,j), D_(k-1)(i,k)+D_(k-1)(k,j)). The outermost k loop corresponds to the proof's allowed-intermediate set.

Why It Matters Here​

This is a concrete bridge to dynamic programming. The state has semantic meaning; reordering loops for convenience without a new proof can make one pass insufficient. O(V³) arithmetic work and O(V²) storage must be affordable before choosing it.

Concrete Examples​

With edges 0→1:4,1→2:-2,0→2:9, allowing intermediate 1 improves 0→2 to 2. If there are parallel 0→1 edges of weights 4 and 7, initialization retains 4, independent of input order. If 2→2 has weight -1, setting the diagonal back to zero after adding edges would hide that cycle.

After the algorithm, any k with D(k,k)<0 lies on or is affected by a negative cycle. Pair (i,j) is unbounded exactly when i can reach such a k and k can reach j. Preserve the reachability relation before propagating status so unreachable and unbounded entries remain distinct.

Common Confusion / Misconceptions​

Boolean reachability uses OR/AND; minimax paths use min/max with suitable identities. Highest-product reliability uses max/product under its probability model, not sum/product. Sum/product counts or sums contributions and is not automatically a highest-probability path algorithm; cycles can complicate even that interpretation. Do not substitute operators without defining the state.

How To Use It​

For a path witness, retain a next-edge or predecessor structure with stable edge identity. Never reconstruct a finite optimum for an unbounded pair. The lab checker uses a small matrix-DP oracle independently of the Bellman–Ford implementation, but the oracle itself still needs hand checks and scoped claims.

Check Yourself​

  1. Why must initialization take minima after setting diagonals?
  2. Why is k the outer loop in this recurrence?
  3. Which pairs are affected by one negative diagonal?
  4. Why does sum/product not maximize a path's probability?

Mini Drill or Application​

Implement the distance-only recurrence as an extension. Compare every source row against Bellman–Ford on small graphs; add a disconnected negative self-loop and verify unaffected pairs stay finite/unreachable as appropriate. Document where the two implementations share assumptions and could share a mistake. See P12.

Read This Only If Stuck​

Find Floyd–Warshall states, initialization, and path algebras in Skiena, CLRS, or Sedgewick and Wayne. These are book indexes, not exact section links. The reading guide names bounded assignments and local source files. Attempt the worked examples before adding more reading.