Floyd Warshall Algorithm

Grokking Graph Algorithms for Coding Interviews

Ask Author

Back to course home

0% completed

Vote For New Content

Floyd Warshall Algorithm

Table of Contents

Contents are not accessible

The Floyd-Warshall algorithm is a fundamental algorithm in computer science used for finding shortest paths in a weighted graph with positive or negative edge weights (but no negative cycles). It is particularly useful for dense graphs where we need to compute shortest paths between all pairs of vertices. The algorithm works by progressively improving the estimate of the shortest path between any two vertices by considering all possible paths through intermediate vertices.

Goal: To find the shortest path between all pairs of vertices in a weighted graph.
Approach: Dynamic Programming. The algorithm iteratively updates the shortest path estimates by considering paths that pass through intermediate vertices.

The Floyd-Warshall algorithm uses a distance matrix, where the entry at row i and column j represents the shortest distance from vertex i to vertex j. Initially, this matrix is populated with direct edge weights, and the algorithm systematically updates it to reflect the shortest paths considering all possible intermediate vertices.

Step-by-Step Algorithm

Initialize the Distance Matrix:
- Create a matrix to store the shortest distances between all pairs of vertices.
- Initialize the matrix with the input graph’s edge weights. Use a large value (INF) to represent the absence of an edge.
Iterate Over All Pairs of Vertices:
- For each pair of vertices (i, j), update the distance between them considering each vertex as an intermediate vertex.
- If the path from i to j through vertex k is shorter than the direct path from i to j, update the distance matrix.
Update Distance Matrix:
- For each pair of vertices (i, j), update the distance as: $( \text{distance}[i][j] = \min(\text{distance}[i][j], \text{distance}[i][k] + \text{distance}[k][j]) )$
- Repeat this process for all vertices as the intermediate vertex.
Print the Final Distance Matrix:
- After processing all vertices, the distance matrix will contain the shortest distances between all pairs of vertices.

Algorithm Walkthrough

Consider the example graph represented by the following adjacency matrix:

Graph:
{
    { 0, 2, INF, 6 },
    { INF, 0, 3, 8 },
    { INF, INF, 0, 1 },
    { INF, INF, INF, 0 }
}

Initialize the Distance Matrix:

Distance Matrix:
{
    { 0, 2, INF, 6 },
    { INF, 0, 3, 8 },
    { INF, INF, 0, 1 },
    { INF, INF, INF, 0 }
}

Iterate Over All Pairs of Vertices:

Using Vertex 0 as Intermediate:

Updated Distance Matrix:
{
    { 0, 2, INF, 6 },
    { INF, 0, 3, 8 },
    { INF, INF, 0, 1 },
    { INF, INF, INF, 0 }
}
(No change since there are no shorter paths through vertex 0)

Using Vertex 1 as Intermediate:

Updated Distance Matrix:
{
    { 0, 2, 5, 6 },
    { INF, 0, 3, 8 },
    { INF, INF, 0, 1 },
    { INF, INF, INF, 0 }
}
(Distance from 0 to 2 updated from INF to 5 through vertex 1)

Using Vertex 2 as Intermediate:

Updated Distance Matrix:
{
    { 0, 2, 5, 6 },
    { INF, 0, 3, 4 },
    { INF, INF, 0, 1 },
    { INF, INF, INF, 0 }
}
(Distance from 1 to 3 updated from 8 to 4 through vertex 2)

Using Vertex 3 as Intermediate:

Final Distance Matrix:
{
    { 0, 2, 5, 6 },
    { INF, 0, 3, 4 },
    { INF, INF, 0, 1 },
    { INF, INF, INF, 0 }
}
(No further changes)

Print the Final Distance Matrix:
- The final distance matrix represents the shortest distances between all pairs of vertices in the graph.

Code

Python3

. . . .

Complexity Analysis

Time Complexity

The Floyd-Warshall algorithm runs in $O(V^3)$ time, where (V) is the number of vertices in the graph. This is because the algorithm consists of three nested loops, each running (V) times.

Space Complexity

The space complexity is $O(V^2)$ because we need to store the distance matrix, which holds the shortest distances between every pair of vertices.

Differences Between Dijkstra's, Bellman-Ford, and Floyd-Warshall Algorithms

Feature	Dijkstra's Algorithm	Bellman-Ford Algorithm	Floyd-Warshall Algorithm
Purpose	Single-source shortest path for all nodes in a graph	Single-source shortest path for all nodes in a graph	All-pairs shortest path for all nodes in a graph
Graph Type	Works only with non-negative weights	Handles both positive and negative weights (no negative cycles)	Handles both positive and negative weights (no negative cycles)
Time Complexity	$O(V^2)$ for matrix representation, $O(E + V \log V)$ with a min-heap	$O(VE)$	$O(V^3)$
Space Complexity	$O(V^2)$ for adjacency matrix, $O(E + V)$ for adjacency list	$O(V)$ for distance array	$O(V^2)$
Dynamic Programming	No	Yes	Yes
Greedy Approach	Yes	No	No
Negative Weights	No	Yes (handles negative weights)	Yes (handles negative weights)
Negative Cycles	No	Detects negative cycles	Detects negative cycles
Use Case	Finding shortest path from a single source to all nodes	Finding shortest path from a single source to all nodes, detecting negative cycles	Finding shortest paths between all pairs of nodes
Optimal for	Dense graphs (with $O(V^2)$ complexity) or sparse graphs with a priority queue	Graphs with negative weights	Dense graphs
Initialization	Initializes distances to infinity except the source node	Initializes distances to infinity except the source node	Initializes the distance matrix with edge weights
Relaxation	Relaxes all edges (V-1) times	Relaxes all edges (V-1) times	Updates shortest paths considering each vertex as an intermediate vertex
Iteration Over Edges	Uses a priority queue to pick the minimum distance vertex	Iterates over all edges	Iterates over all pairs of nodes
Cycle Detection	Not applicable	Detects negative weight cycles	Not applicable (can be used to detect negative cycles)
Algorithm Type	Greedy	Dynamic Programming	Dynamic Programming

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible