Warshall's algorithm with example

Warshall's algorithm finds the transitive closure of a directed graph, i.e. the matrix P where P[i][j] = 1 if there is a path from vertex i to vertex j. Start with the adjacency matrix and, for each vertex k in turn, allow k as an intermediate vertex: a path i → j exists if one already exists, or if i → k and k → j both exist.

WARSHALL(A, n)           // A = adjacency matrix (0/1)
1. P = A
2. for k = 1 to n
3.     for i = 1 to n
4.         for j = 1 to n
5.             P[i][j] = P[i][j] OR (P[i][k] AND P[k][j])
6. return P

void warshall(int p[][N], int n) {
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                p[i][j] = p[i][j] || (p[i][k] && p[k][j]);
}

Time O(n³), space O(n²). After step k, P[i][j] = 1 means a path exists using only vertices 1..k as intermediates.

Example

Directed graph with vertices 1, 2, 3, 4 and edges 1→2, 2→3, 4→1.

 4 -> 1 -> 2 -> 3

Rows and columns are ordered 1, 2, 3, 4.

Transitive closure: 1 reaches 2, 3; 2 reaches 3; 3 reaches none; 4 reaches 1, 2, 3.