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

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

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

The Floyd-Warshall Algorithm is a classic dynamic programming algorithm used to find the shortest paths between all pairs of vertices in a weighted graph.

It works for both directed and undirected graphs and can handle negative edge weights (but no negative cycles).

---

Key Concept:

The Floyd-Warshall Algorithm updates a distance matrix dist[i][j], representing the shortest distance from node i to node j, by checking if an intermediate vertex k provides a shorter path.

---

Algorithm Steps:

Given a graph with V vertices:

1. Initialize the distance matrix:
   • dist[i][j] = weight of edge (i → j)
   • If no direct edge exists: dist[i][j] = ∞
   • dist[i][i] = 0
2. For each vertex k from 0 to V-1:

   for k in range(V):
       for i in range(V):
           for j in range(V):
               if dist[i][j] > dist[i][k] + dist[k][j]:
                   dist[i][j] = dist[i][k] + dist[k][j]
   

---

Practical Example

Given Graph:

Let’s take a graph with 4 nodes: A, B, C, D
Let the initial weighted adjacency matrix be:

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

We use ∞ (infinity) to represent that there is no direct path.

---

Step-by-Step Floyd-Warshall Execution:

We iteratively update the matrix using each node as an intermediate:

Initial Matrix:

0   3   ∞   7
8   0   2   ∞
5   ∞   0   1
2   ∞   ∞   0

After using node A as intermediate (k=0):

0   3   ∞   7
8   0   2   15
5   8   0   1
2   5   ∞   0

After using node B as intermediate (k=1):

0   3   5   7
8   0   2   15
5   8   0   1
2   5   7   0

After using node C as intermediate (k=2):

0   3   5   6
8   0   2   3
5   8   0   1
2   5   7   0

After using node D as intermediate (k=3):

No further updates — final matrix remains:

0   3   5   6
8   0   2   3
5   8   0   1
2   5   7   0

---

Final Output (Shortest Paths Matrix):

From/To	A	B	C	D
A	0	3	5	6
B	8	0	2	3
C	5	8	0	1
D	2	5	7	0

---

Time Complexity:

• O(V³) → efficient for small or medium-sized graphs.
• Not suitable for large sparse graphs; use Dijkstra or Bellman-Ford instead.

---

When to Use:

• Graph has negative edges but no negative cycles
• You want shortest path between all pairs
• Works well for dense graphs (many edges)

---

Would you like a Python implementation or visualization for better understanding?

All Pair Shortest Path Floyd-Warshall Algorithm With Practical Example

DP: All Pairs Shortest Paths, The Floyd-Warshall Algorithm