Please enable JavaScript.
Coggle requires JavaScript to display documents.
Warshall’s and Floyd’s Algorithms - Coggle Diagram
Warshall’s and Floyd’s Algorithms
Warshall’s Algorithm
Definition :check:
Warshall's Algorithm is a method for computing the transitive closure of a directed graph using an iterative approach.
Directed Graph & Adjacency Matrix
A = {aij} with 1 indicating directed edge from vertex i to vertex j
Definition of Transitive Closure Matrix
T = {tij}
tij = 1 if there's a path (positive length) from vertex i to vertex j
Aplications :check:
Dependency tracking
Data flow & control flow analysis
Inheritance testing
Redundancy identification
Test generation for digital circuits
Floyd’s algorithm
Definition :check:
Finding shortest paths between all pairs of vertices in a weighted, connected graph
Aplications :check:
Communications, transportation networks, computer games
Distance Matrix :check:
Matrix D = {dij} where dij is the shortest path length from vertex i to vertex j
Similar to Warshall’s algorithm but for shortest paths instead of transitive closure