Idea Behind Floyd Warshall Algorithm
Suppose we have a graph G[][] with V vertices from 1 to N. Now we have to evaluate a shortestPathMatrix[][] where shortestPathMatrix[i][j] represents the shortest path between vertices i and j.
Obviously the shortest path between i to j will have some k number of intermediate nodes. The idea behind floyd warshall algorithm is to treat each and every vertex from 1 to N as an intermediate node one by one.
The following figure shows the above optimal substructure property in floyd warshall algorithm:
Floyd Warshall Algorithm
The Floyd-Warshall algorithm, named after its creators Robert Floyd and Stephen Warshall, is a fundamental algorithm in computer science and graph theory. It is used to find the shortest paths between all pairs of nodes in a weighted graph. This algorithm is highly efficient and can handle graphs with both positive and negative edge weights, making it a versatile tool for solving a wide range of network and connectivity problems.
Table of Content
- Floyd Warshall Algorithm
- Idea Behind Floyd Warshall Algorithm
- Floyd Warshall Algorithm Algorithm
- Pseudo-Code of Floyd Warshall Algorithm
- Illustration of Floyd Warshall Algorithm
- Complexity Analysis of Floyd Warshall Algorithm
- Why Floyd-Warshall Algorithm better for Dense Graphs and not for Sparse Graphs?
- Important Interview questions related to Floyd-Warshall
- Real World Applications of Floyd-Warshall Algorithm
Contact Us