Floyd Warshall Algorithm
The Floyd Warshall Algorithm is an all pair shortest path algorithm unlike Dijkstra and Bellman Ford which are single source shortest path algorithms. This algorithm works for both the directed and undirected weighted graphs. But, it does not work for the graphs with negative cycles (where the sum of the edges in a cycle is negative). It follows Dynamic Programming approach to check every possible path going via every possible node in order to calculate shortest distance between every pair of nodes.
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