Course contentsShow
← Computer Science
Lesson 998 of 2,87223. Shortest Path AlgorithmsFree lesson

Transitive Closure with Floyd-Warshall

Adapting Floyd-Warshall to compute reachability information between all vertex pairs.

Transitive Closure with Floyd-Warshall

What you'll learn: How to adapt the Floyd-Warshall algorithm to determine which vertices can reach which other vertices, ignoring edge weights entirely.

The Core Idea

You've just learned Floyd-Warshall computes shortest paths between all vertex pairs. But sometimes you don't care how far apart vertices are—you only want to know: "Can I get from vertex A to vertex B at all?"

This yes/no reachability question is called transitive closure. Think of it like a social network: instead of measuring degrees of separation, you simply want to know "Is person A connected to person B through any chain of friendships?"

From Distances to Reachability

The beautiful part: Floyd-Warshall's structure works perfectly for this! Instead of storing distances, store boolean values:

  • reach[i][j] = true if there's any path from i to j
  • reach[i][j] = false otherwise

The update rule changes from minimizing distance to logical OR:

reach[i][j] = reach[i][j] OR (reach[i][k] AND reach[k][j])

Translation: "You can reach j from i if you already could, OR if you can reach some intermediate vertex k from i AND reach j from k."

Why This Works

Floyd-Warshall considers each vertex as a potential intermediate step. For transitive closure, if a path exists through vertex k, then reachability becomes true—and once true, it stays true. The triple-nested loop structure remains identical; only the operation inside changes.

Key Takeaway: Transitive closure is Floyd-Warshall simplified to boolean reachability—replace distance minimization with logical OR to answer "can I get there?" for all vertex pairs in O(V³) time.