All Pair Shortest Path Floyd-Warshall Algorithm With Practical Example

All Pair Shortest Path Floyd-Warshall Algorithm With Practical Example

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 vertex i to j.
• The algorithm follows the principle: $$\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 and j, set dist[i][j] to its weight.
• If i == j, set dist[i][j] = 0.
• If there is no direct edge, set dist[i][j] = ∞.

Iterate through all nodes as intermediate vertices:

• For each vertex k, update dist[i][j] for all pairs (i, j).
• Use the formula: $$\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):

(∞ 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 than 2
• 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: $$\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?

All Pair Shortest Path Floyd-Warshall Algorithm With Practical Example

Implementation Floyd-Warshall Algorithm for the Shortest …

All-pair shortest Path (Floyd-Warshall Algorithm)

Algorithms II, CS 502 – All-Pairs Shortest Paths

Chapter 5: Floyd’s Algorithm