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] = trueif there's any path fromitojreach[i][j] = falseotherwise
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.