GraphLab › Warshall's algorithm
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.
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.
Each step uses one more vertex as k and highlights the cells that change, with the path that made each one 1.