All Pair Shortest Path Floyd-Warshall Algorithm With Practical Example
Contents
- 1 All-Pairs Shortest Path: Floyd-Warshall Algorithm
- 2 Key Concepts
- 3 Algorithm Steps
- 4 Practical Example
- 5 Example Graph (Adjacency Matrix Representation)
- 6 Step-by-Step Execution
- 7 Time Complexity
- 8 Advantages
- 9 Disadvantages
- 10 Python Implementation
- 11 Summary
- 12 All Pair Shortest Path Floyd-Warshall Algorithm With Practical Example
- 13 Implementation Floyd-Warshall Algorithm for the Shortest …
- 14 All-pair shortest Path (Floyd-Warshall Algorithm)
- 15 Algorithms II, CS 502 – All-Pairs Shortest Paths
- 16 Chapter 5: Floyd’s Algorithm
All-Pairs Shortest Path: Floyd-Warshall Algorithm
The Floyd-Warshall algorithm is a dynamic programming technique used to find the shortest paths between all pairs of vertices in a weighted graph. It works for both directed and undirected graphs with positive or negative weights (but no negative cycles).
Key Concepts
- The algorithm repeatedly updates the shortest path between every pair of vertices by considering intermediate nodes.
- It uses a distance matrix where each cell
(i, j)
represents the shortest distance from vertexi
toj
. - The algorithm follows the principle: dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])\text{dist}[i][j] = \min(\text{dist}[i][j], \text{dist}[i][k] + \text{dist}[k][j]) where
k
is an intermediate node.
Algorithm Steps
Initialize the distance matrix:
- If there is a direct edge between
i
andj
, setdist[i][j]
to its weight. - If
i == j
, setdist[i][j] = 0
. - If there is no direct edge, set
dist[i][j] = ∞
.
Iterate through all nodes as intermediate vertices:
- For each vertex
k
, updatedist[i][j]
for all pairs(i, j)
. - Use the formula: dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])\text{dist}[i][j] = \min(\text{dist}[i][j], \text{dist}[i][k] + \text{dist}[k][j])
- This checks if a shorter path exists via
k
.
After all iterations, dist[i][j]
will contain the shortest path from i
to j
.
Practical Example
Example Graph (Adjacency Matrix Representation)
We have a directed graph with 4 vertices (A, B, C, D):
From → To | A | B | C | D |
---|---|---|---|---|
A | 0 | 3 | ∞ | 7 |
B | 8 | 0 | 2 | ∞ |
C | 5 | ∞ | 0 | 1 |
D | 2 | ∞ | ∞ | 0 |
(∞ represents no direct edge between the nodes)
Step-by-Step Execution
Initial Distance Matrix
Step 1: Consider Node A (k = 0)
- No improvement in paths via A.
Step 2: Consider Node B (k = 1)
- Path C → B via A:
5 + 3 = 8
, shorter than∞
- Updated matrix:
Step 3: Consider Node C (k = 2)
- Path B → D via C:
2 + 1 = 3
, shorter than∞
- Updated matrix:
Step 4: Consider Node D (k = 3)
- Path A → C via D:
7 + 1 = 6
, shorter than∞
- Path B → C via D:
3 + 1 = 4
, shorter than2
- Updated matrix:
Final matrix gives the shortest path between every pair of nodes.
Time Complexity
The Floyd-Warshall algorithm runs in O(V³) time complexity, where V
is the number of vertices.
Advantages
Simple and easy to implement
Works with negative weights (but no negative cycles)
Finds shortest paths for all pairs in one execution
Disadvantages
Does not work with graphs containing negative cycles
Less efficient than Dijkstra’s Algorithm for sparse graphs
Python Implementation
Output
Summary
- The Floyd-Warshall Algorithm efficiently finds shortest paths between all pairs of vertices.
- It follows the formula: dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j])\text{dist}[i][j] = \min(\text{dist}[i][j], \text{dist}[i][k] + \text{dist}[k][j])
- Time Complexity: O(V³)
- Best for: Dense graphs and graphs with negative weights (no negative cycles).
Would you like a real-world example or a C/C++ implementation?