Warshall’s Algorithm

 

🔹 Warshall’s Algorithm (Transitive Closure) 🚀

Warshall’s Algorithm is used to compute the transitive closure of a directed graph. It determines whether a path exists between every pair of nodes.

---

🔹 How It Works

Given a graph represented as an adjacency matrix, Warshall’s algorithm updates the matrix to indicate whether a path exists between each pair of vertices.

✅ Input: A boolean adjacency matrix (1 if there is an edge, 0 if there is none).
✅ Output: The transitive closure matrix, where reach[i][j] = 1 if there exists a path from i to j.
✅ Time Complexity: O(V³) (since it uses three nested loops).

---

🔹 Algorithm Steps

1️⃣ Initialize the adjacency matrix reach[][] (1 if an edge exists, else 0).
2️⃣ Iterate over all intermediate nodes (k):

• For every pair of vertices (i, j), check if going through k provides a shorter path.
• If reach[i][k] = 1 and reach[k][j] = 1, then set reach[i][j] = 1.
  3️⃣ Final matrix shows if a path exists between any two vertices.

---

🔹 Python Implementation

def warshall_algorithm(graph):
    V = len(graph)  # Number of vertices
    reach = [row[:] for row in graph]  # Copy of the input graph

    for k in range(V):  # Intermediate node
        for i in range(V):  # Start node
            for j in range(V):  # End node
                reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j])

    return reach

# Example graph (Adjacency Matrix)
graph = [
    [1, 1, 0, 1],
    [0, 1, 1, 0],
    [0, 0, 1, 1],
    [0, 0, 0, 1]
]

result = warshall_algorithm(graph)

# Print the transitive closure matrix
for row in result:
    print(row)

---

🔹 Example

Input Graph (Adjacency Matrix)

   0  1  2  3
0 [1, 1, 0, 1]
1 [0, 1, 1, 0]
2 [0, 0, 1, 1]
3 [0, 0, 0, 1]

Transitive Closure Output

[1, 1, 1, 1]
[0, 1, 1, 1]
[0, 0, 1, 1]
[0, 0, 0, 1]

This means that from node 0, we can reach all other nodes.

---

🔹 Applications of Warshall’s Algorithm

✅ Database Systems: Finding indirect relationships (e.g., foreign key dependencies).
✅ Computer Networks: Identifying reachable nodes in a network.
✅ Social Networks: Finding if a person can be connected via mutual friends.
✅ Compiler Optimization: Analyzing dependencies between code statements.