[go: up one dir, main page]
Scribd
Upload
61 views5 pages

Warshall's Algorithm

Warshall's Algorithm is used to compute the transitive closure of a directed graph with n vertices, represented as an n × n boolean matrix. In this matrix, an element is 1 if there exists a nontrivial path from one vertex to another, otherwise it is 0. The document briefly outlines the definition and purpose of the algorithm.

Uploaded by

Ms. Pavithra D
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
61 views5 pages

Warshall's Algorithm

Warshall's Algorithm is used to compute the transitive closure of a directed graph with n vertices, represented as an n × n boolean matrix. In this matrix, an element is 1 if there exists a nontrivial path from one vertex to another, otherwise it is 0. The document briefly outlines the definition and purpose of the algorithm.

Uploaded by

Ms. Pavithra D
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 5

Warshall’s Algorithm

Jeevitha S
Definition

The transitive closure of a directed graph with n


vertices can be defined as the n × n boolean
matrix T = {tij }, in which the element in the ith
row and the j th column is 1 if there exists a
nontrivial path (i.e., directed path of a positive
length) from the ith vertex to the j th vertex;
otherwise, tij is 0.
Warshall’s Algorithm
Algorithm
THANK YOU!!!

You might also like