---
title: "Warshall's algorithm with example"
subject: "Data Structure and Algorithm"
chapter: 10
key: "semester_4/data_structure_and_algorithm:warshall-algorithm-example"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/warshall-algorithm-example
site: BCT Engineering
---

# Warshall's algorithm with example

Data Structure and Algorithm · Chapter 10: Graphs

- Asked in: 2075 Baisakh, 6 marks; 2073 Bhadra, 3 marks (asked 2 times)
- Video: [Warshall's Algorithm (Finding the Transitive Closure)](https://www.youtube.com/watch?v=_-p8zhizock) — Neso Academy
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/warshall-algorithm-example
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-10

## Question

Write an algorithm for Warshall's algorithm and illustrate with an example.

## Short answer

Warshall's algorithm computes transitive closure using triple nested loops: for each k, set P[i][j] = P[i][j] OR (P[i][k] AND P[k][j]). Example: directed edges 1→2, 2→3, 4→1 yield closure where 1 reaches 2,3; 2 reaches 3; 4 reaches 1,2,3.

## Answer

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.

```text
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
```
```c
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.

```text
 4 -> 1 -> 2 -> 3
```
Rows and columns are ordered 1, 2, 3, 4.

| Matrix | Row 1 | Row 2 | Row 3 | Row 4 | Change |
|---|---|---|---|---|---|
| P₀ (adjacency) | 0 1 0 0 | 0 0 1 0 | 0 0 0 0 | 1 0 0 0 | initial |
| P₁ (via 1) | 0 1 0 0 | 0 0 1 0 | 0 0 0 0 | 1 1 0 0 | 4→1→2 gives 4→2 |
| P₂ (via 2) | 0 1 1 0 | 0 0 1 0 | 0 0 0 0 | 1 1 1 0 | 1→2→3 gives 1→3; 4→2→3 gives 4→3 |
| P₃ (via 3) | 0 1 1 0 | 0 0 1 0 | 0 0 0 0 | 1 1 1 0 | no change (3 has no outgoing edge) |
| P₄ (via 4) | 0 1 1 0 | 0 0 1 0 | 0 0 0 0 | 1 1 1 0 | no change (no edge enters 4) |

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

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What does Warshall's algorithm compute?
   A. Shortest path tree
   B. The transitive closure (reachability matrix)
   C. Minimum spanning tree
   D. Topological order
   Answer: B. P[i][j] = 1 if a path exists from i to j. (Key point: Purpose)

2. What is the update at step k?
   A. P[i][j] = P[i][j] AND P[i][k]
   B. P[i][j] = P[i][k] + P[k][j] always
   C. P[i][j] = P[i][j] OR (P[i][k] AND P[k][j])
   D. P[i][j] = NOT P[i][j]
   Answer: C. Path exists directly or via k. (Key point: Update rule)

3. What is the time complexity?
   A. O(n)
   B. O(n^2)
   C. O(n log n)
   D. O(n^3)
   Answer: D. Three nested loops. (Key point: Complexity)

4. For edges 1->2, 2->3, 4->1, which vertices does 4 reach?
   A. 1, 2 and 3
   B. Only 1
   C. Only 3
   D. None
   Answer: A. 4->1->2->3. (Key point: Example result)

## Related in Data Structure and Algorithm

- [Transitive closure of 4-vertex graph (Warshall)](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Atransitive-closure-warshall-abcd) — Data Structure and Algorithm, chapter 10, asked 2×
- [Transitive closure of 5-vertex graph (Warshall)](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Atransitive-closure-warshall-abcde) — Data Structure and Algorithm, chapter 10, asked 2×