Renowned in computer science and graph theory for its founders, Robert Floyd and Stephen Warshall, the Floyd-Warshall algorithm is a basic tool. In a weighted graph, it determines the shortest pathways between all pairings of nodes. Extremely efficient and able to manage graphs with both positive and negative edge weights, this method is a flexible tool for addressing a broad spectrum of network and connection issues.
Floyd Warshall Algorithm:
Unlike single source shortest path methods including Dijkstra and Bellman Ford, the Floyd Warshall Algorithm is an all pair shortest path algorithm. Both directed and undirected weighted graphs are covered by this method. It does not apply, though, for graphs with negative cycles—that is, where the total of the edges in a cycle is negative. To find the shortest distance between any pair of nodes, it uses a dynamic programming method checking every conceivable path passing via every other node.
Floyd Warshall Algorithm Algorithm:
- Start with the solution matrix same as the input graph matrix.
- Then change the solution matrix to view all vertices as an intermediary vertex.
- One picks all vertices one by one and updates all shortest paths including the chosen vertex as an intermediary vertex in the shortest path.
- We previously have considered vertices {0, 1, 2,.. k-1} as intermediate vertices when we choose vertex number k as such.
- Two alternative situations exist for every pair (i, j) of the source and destination vertices correspondingly.
- k is not a shortest path’s intermediate vertex from i to j. We preserve the value of dist[i][j] exactly.
- k is a shortest path intermediate vertex between i and j. If dist[i][j] > dist[i][k] + dist[k][j] then we update dist[i][j] as dist[i][k] + dist[k][j].
Pseudo-Code of Floyd Warshall Algorithm :
For k = 0 to n – 1
For i = 0 to n – 1
For j = 0 to n – 1
Distance[i, j] = min(Distance[i, j], Distance[i, k] + Distance[k, j])
where i = source Node, j = Destination Node, k = Intermediate NodeTime Complexity
Time Complexity: O(V3), where V is the number of vertices in the graph and we perform three nested loops each of size V Auxiliary Space: O(V2), to generate a 2-D matrix in order to save the shortest distance for every pair of nodes.
Note: The programme above merely shows the shortest distances. Storing the precursor information in a separate 2D matrix will help us to publish the shortest paths as well.
Why, for Dense Graphs rather than for Sparse Graphs, Floyd-Warshall Algorithm is better?
Dense graphs are those in which the number of edges is noticeably considerably more than the number of vertices.
A sparse graph is one in which there are quite few edges.
The Floyd Warshall Algorithm runs for O(V3) times regardless of the number of edges in the graph, so it is most appropriate for dense graphs. Regarding sparse graphs, Johnson’s Algorithm is more appropriate.