PadhaikoAll subjects

Past exam question: 2075 Baisakh (Back), Q10

Data Structure and Algorithms · 6 marks

Open in the Padhaiko app

Topic: Graphs

Question

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

Solution

Warshall's Algorithm for Transitive Closure: Given an adjacency matrix of a directed graph , Warshall's algorithm computes the reachability matrix in time:

Algorithm WARSHALL(A, n):
1. R = copy of A
2. For k = 0 to n - 1:
       For i = 0 to n - 1:
           For j = 0 to n - 1:
               R[i][j] = R[i][j] OR (R[i][k] AND R[k][j])
3. Return R

Worked Example on a 3-Vertex Directed Graph (0 -> 1, 1 -> 2): Initial adjacency matrix :

Answer:

Warshall's algorithm updates for each intermediate vertex in time, discovering indirect paths such as ().

All past exam questions for Data Structure and Algorithms