All Pair Shortest Path Floyd-Warshall Algorithm With Practical Example

Ali Seron Jason

1 week ago

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

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: $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 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: $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 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

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

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?

All Pair Shortest Path Floyd-Warshall Algorithm With Practical Example

All-Pairs Shortest Path: Floyd-Warshall Algorithm

Key Concepts

Algorithm Steps

Practical Example

Example Graph (Adjacency Matrix Representation)

Step-by-Step Execution

Initial Distance Matrix

Step 1: Consider Node A (k = 0)

Step 2: Consider Node B (k = 1)

Step 3: Consider Node C (k = 2)

Step 4: Consider Node D (k = 3)

Time Complexity

Advantages

Disadvantages

Python Implementation

Summary

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