Dynamic Programming: Warshall’s algorithmApply Warshall’s algorithm to find the transitive closure of the digraph defined by thefollowing adjacency matrix:[[0,0,0,1],[0,0,1,0],[0,0,0,1],[0,0,0,0]]
Question
Dynamic Programming: Warshall’s algorithmApply Warshall’s algorithm to find the transitive closure of the digraph defined by thefollowing adjacency matrix:[[0,0,0,1],[0,0,1,0],[0,0,0,1],[0,0,0,0]]
Solution
Warshall's algorithm is used to find the transitive closure of a directed graph. The transitive closure of a graph is a matrix that tells us if there is a path from any vertex to any other vertex.
Here is the step-by-step process of applying Warshall's algorithm to the given adjacency matrix:
-
Initialize the solution matrix same as the input graph matrix.
We are given the following adjacency matrix:
0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0So, our initial solution matrix is the same as the above.
-
Then we update the solution matrix by considering all vertices as an intermediate vertex. The idea is to one by one pick all vertices and update all shortest paths which include the picked vertex as an intermediate vertex.
We do the following for every vertex
k.For every pair
(i, j)of the source and destination vertices respectively, there are two possible cases:kis not an intermediate vertex in shortest path fromitoj. We keep the value ofitojas it is.kis an intermediate vertex in shortest path fromitoj. We update the value ofitojasitokORktoj.
For
k=0, the matrix doesn't change as there are no paths from0.For
k=1, the matrix doesn't change as there are no paths from1.For
k=2, we update the path from1to3as there is a path from1to2and from2to3. The matrix becomes:0 0 0 1 0 0 1 1 0 0 0 1 0 0 0 0For
k=3, the matrix doesn't change as there are no paths from3. -
Finally, we get the following transitive closure of the given graph.
0 0 0 1 0 0 1 1 0 0 0 1 0 0 0 0
So, the transitive closure of the given digraph is:
0 0 0 1
0 0 1 1
0 0 0 1
0 0 0 0
Similar Questions
Use Warshall's algorithm to compute the transitive closure of the graph with the following adjacency matrix: 0 0 1 1 1 0 0 1 0 0 0 0 0 1 1 0 Choose the correct values for the unknown variables after each of the four steps for the algorithm. After the first step: 0 0 1 1 1 a1 b1 1 0 0 0 0 c1 1 1 0 [ Select ] After the second step: 0 0 1 1 1 a2 b2 1 0 0 0 0 c2 1 1 1 [ Select ] After the third step: 0 0 1 1 1 a3 b3 1 0 0 0 0 c3 1 1 1 [ Select ] After the fourth and final step: 1 1 1 1 1 a4 b4 1 0 0 0 0 c4 1 1 1 [ Select ]
Which of the following pseudocode correctly represents the initialization step of the Warshall algorithm for finding the transitive closure of a graph?Marks : 1Negative Marks : 0Answer hereProcedure WarshallInit(Graph G): For each vertex v in G: For each vertex u in G: If u is adjacent to v: Set distance[u][v] to 1 Else: Set distance[u][v] to 0Procedure WarshallInit(Graph G): For each vertex u in G: For each vertex v in G: If u is adjacent to v: Set distance[u][v] to 1 Else: Set distance[u][v] to infinityProcedure WarshallInit(Graph G): For each vertex v in G: For each vertex u in G: If u is adjacent to v: Set distance[v][u] to 0 Else: Set distance[v][u] to 0Procedure WarshallInit(Graph G): For each vertex u in G: For each vertex v in G: If u is adjacent to v: Set distance[v][u] to 1 Else: Set distance[v][u] to infinity
If a graph has 'n' vertices, what is the maximum size of the matrix required to represent its transitive closure using the Warshall algorithm?
The Warshall algorithm uses ____ nested loops to compute the transitive closure.
Consider a directed graph with six vertices. The initial adjacency matrix is given below. After applying the Warshall algorithm, how many entries in the resulting adjacency matrix will be '1'?Initial Adjacency Matrix: | 1 2 3 4 5 6----------------1 | 0 1 0 1 0 02 | 0 0 1 0 0 03 | 0 0 0 0 1 14 | 0 0 0 0 0 05 | 0 0 0 1 0 06 | 0 0 0 0 0 0
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.