GraphLab

Graph theory & algorithm visualizer
About Warshall's algorithm

GraphLab › Warshall's algorithm

Warshall's Algorithm: Path Matrix and Transitive Closure Step by Step

Warshall's algorithm finds the path matrix of a directed graph, also called its transitive closure: entry (i, j) is 1 when there is a path from vertex i to vertex j, and 0 otherwise.

How it works

Start with the adjacency matrix W₀. For each vertex k in turn, allow paths to pass through k:

Wk[i][j] = Wk−1[i][j] ∨ ( Wk−1[i][k] ∧ Wk−1[k][j] )

After every vertex has been used as k, the matrix shows every pair that is joined by a path. The same idea with sums and minimums instead of "or" and "and" gives the Floyd–Warshall shortest path algorithm.

Try it in GraphLab

Each step uses one more vertex as k and highlights the cells that change, with the path that made each one 1.

More topics