DIZNR INTERNATIONAL

All Pair Shortest Path Floyd-Warshall Algorithm With Practical Example

All Pair Shortest Path Floyd-Warshall Algorithm With Practical Example

https://www.gyanodhan.com/video/7B1.%20GATE%20CSEIT/Algorith%20Analysis%20and%20Design/622.%20AAD-%20All%20Pair%20Shortest%20Path%20%20%20Floyd-Warshall%20Algorithm%20%20%20With%20Practical%20Example%20%2035.mp4

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

 Algorithm Steps

Initialize the distance matrix:

Iterate through all nodes as intermediate vertices:

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

A B C D
A [ 0 3 ∞ 7 ]
B [ 8 0 2 ∞ ]
C [ 5 ∞ 0 1 ]
D [ 2 ∞ ∞ 0 ]

Step 1: Consider Node A (k = 0)

Step 2: Consider Node B (k = 1)

A B C D
A [ 0 3 ∞ 7 ]
B [ 8 0 2 ∞ ]
C [ 5 8 0 1 ]
D [ 2 ∞ ∞ 0 ]

Step 3: Consider Node C (k = 2)

A B C D
A [ 0 3 5 7 ]
B [ 8 0 2 3 ]
C [ 5 8 0 1 ]
D [ 2 ∞ ∞ 0 ]

Step 4: Consider Node D (k = 3)

A B C D
A [ 0 3 5 6 ]
B [ 5 0 2 3 ]
C [ 5 8 0 1 ]
D [ 2 5 7 0 ]

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

import numpy as np

# Number of vertices
V = 4
INF = float('inf')

# Adjacency matrix representation of the graph
graph = [[0, 3, INF, 7],
[8, 0, 2, INF],
[5, INF, 0, 1],
[2, INF, INF, 0]]

def floyd_warshall(graph):
dist = np.array(graph) # Copy graph into dist matrix

for k in range(V): # Intermediate vertices
for i in range(V): # Source vertex
for j in range(V): # Destination vertex
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

return dist

# Compute shortest paths
shortest_paths = floyd_warshall(graph)

# Display the result
print("All-Pairs Shortest Path Matrix:")
print(shortest_paths)

Output

All-Pairs Shortest Path Matrix:
[[ 0. 3. 5. 6.]
[ 5. 0. 2. 3.]
[ 5. 8. 0. 1.]
[ 2. 5. 7. 0.]]

 Summary

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