Transitive closure of 5-vertex graph (Warshall)

Vertices in order a, b, c, d, e. Edges: a→c, b→c, b→d, c→d, d→e. For each k in turn, P[i][j] = P[i][j] OR (P[i][k] AND P[k][j]).

Initial graph

a --> c --> d --> e
      ^     ^
      |     |
      b ----+
   (b -> c and b -> d)

P₀ (adjacency matrix)

k = a: no edge enters a, so no change. k = b: no edge enters b, so no change.

k = c: into c: a, b. c's row has d. So a→d is added (b→d already exists).

k = d: into d: a, b, c. d's row has e. So a→e, b→e and c→e are added.

k = e: e has no outgoing edge, so no change. This is the final matrix (the transitive closure).

Final graph (transitive closure)

Edges: a→c, a→d, a→e, b→c, b→d, b→e, c→d, c→e, d→e (nine edges; the new ones are a→d, a→e, b→e, c→e).

Original edges: a->c  b->c  b->d  c->d  d->e
Added edges:    a->d  a->e  b->e  c->e

Final graph (out-edges of each vertex):
 a ----> c, d, e
 b ----> c, d, e
 c ----> d, e
 d ----> e
 e       (no outgoing edges)

In words: a reaches c, d, e; b reaches c, d, e; c reaches d, e; d reaches e; e reaches nothing.