Warshall’s Algorithm Explained in 5 Minutes | Python Code + Dry Run | CodeWithBV
Description
Initialize the Graph:
We start with a directed graph represented as an adjacency matrix. In this matrix, graph[i][j] is 1 if there's a directed edge from node i to node j, and 0 otherwise.
Create a Transitive Closure Matrix:
We create an empty matrix called transitive that initially has the same values as the original graph. This matrix will be used to store information about the reachability between nodes.
Apply Warshall's Algorithm:
We iterate through all pairs of nodes (i and j) and an intermediate node (k).
We check if there's a path from i to j through k. If i can reach k and k can reach j, we mark a path from i to j in the transitive matrix.
Display Transitive Closure:
We define a function to display the transitive closure matrix. Each element in the matrix will tell us whether there is a path from node i to node j.
Example Usage:
We provide an example directed graph as the graph variable. You can replace it with your own graph. Then, we call the transitive_closure function to compute the transitive closure and display the result using the print_transitive_closure function.
Output:
The output is a matrix (the transitive closure) that shows which nodes can be reached from other nodes in the graph. If there's a path from node i to node j, the corresponding element in the matrix is 1, and if there's no path, it's 0.