The Floyd-Warshall algorithm is a classical algorithm for finding the shortest paths between all

pairs of nodes in a graph. It is particularly useful in solving problems like all-pairs shortest
path and can handle graphs with negative edge weights, but it does not work well if there are
negative weight cycles.
In the context of network flow problems, the Floyd-Warshall algorithm is not directly used for
flow computations. However, it is helpful in finding the shortest path in a weighted directed
graph with both positive and negative weights. This can be useful in routing problems, where
you need to find the shortest paths between pairs of nodes.
The Floyd-Warshall algorithm is used to find the shortest paths between all pairs of vertices in
a weighted graph, with negative edges allowed. Here is a step-by-step numerical example.

Example 1
Consider the following weighted directed graph with 4 vertices A,B,C,D:

From To Weight

A B 3

A C ∞ (no edge)

A D 7

B A 8

B C 2

B D ∞ (no edge)

C A 5

C B ∞ (no edge)

C D 1

D A 2

D B ∞ (no edge)

D C ∞ (no edge)

1
Step 1: Representation as a Distance Matrix
We represent the graph as an adjacency matrix, where:
 dist[i][j] = weight of the edge from node i to node j (or ∞\infinity ∞ if no edge exists).
 dist[i][i] = 0 for all i (distance from a node to itself).
Initial distance matrix:

Step 2: Algorithm Execution

The algorithm iteratively updates the distance matrix by considering each vertex k as an
intermediate vertex. For each pair of vertices i,j, update:
dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
Iteration 1 (Using k = A)
Update all dist[i][j] by considering paths through A:
dist[i][j] = min(dist[i][j], dist[i][A]+dist[A][j])
Updated matrix:

2
Iteration 2 (Using k = B)
Update all dist[i][j] by considering paths through B:
dist[i][j] = min(dist[i][j], dist[i][B]+dist[B][j])
Updated matrix:

Iteration 3 (Using k = C)
Update all dist[i][j] by considering paths through C:
dist[i][j] = min(dist[i][j], dist[i][C]+dist[C][j])
Updated matrix:

Iteration 4 (Using k = D)
Update all dist[i][j] by considering paths through D:
dist[i][j] = min(dist[i][j], dist[i][D]+dist[D][j])
Updated matrix:

Step 3: Final Distance Matrix

3
The final distance matrix represents the shortest distances between all pairs of vertices:

Shortest Paths
 A → B: 3
 A → C: 5
 A → D: 6
This shows how the algorithm efficiently calculates shortest paths between all nodes.

Python Code
# Define infinity as a large number
INF = float('inf')

# Given adjacency matrix for the graph

graph = [
[0, 3, INF, 7], # A → A, B, C, D
[8, 0, 2, INF], # B → A, B, C, D
[5, INF, 0, 1], # C → A, B, C, D
[2, INF, INF, 0] # D → A, B, C, D
]

def floyd_warshall(graph):
V = len(graph) # Number of vertices
dist = [row[:] for row in graph] # Copy of the original graph

# Floyd-Warshall Algorithm
for k in range(V): # Intermediate node
for i in range(V): # Start node
for j in range(V): # End node
# Update dist[i][j] if a shorter path is found via node k
if dist[i][k] != INF and dist[k][j] != INF:
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

return dist

# Compute shortest paths

shortest_paths = floyd_warshall(graph)

# Print the final shortest path matrix

4
print("Shortest path matrix:")
for row in shortest_paths:
print(row)

Explanation of the Code

1. Initialize the Graph

o We represent the graph as an adjacency matrix.
o If there's no direct edge between two nodes, we set the weight as infinity (INF).
2. Floyd-Warshall Algorithm Steps
o It checks if using an intermediate node results in a shorter path between two
nodes.
o The shortest paths are stored in a distance matrix (dist), which is updated
during each iteration.
3. Final Output
o The program prints the shortest path matrix, where each value represents the
shortest distance between two nodes.

Expected Output (Corrected Shortest Paths)

The program will print:

csharp
CopyEdit
Shortest path matrix:
[0, 3, 5, 6]
[5, 0, 2, 3]
[3, 6, 0, 1]
[2, 5, 7, 0]

Example 2
Consider the following weighted directed graph with 5 vertices A,B,C,D,E:

From To Weight

A B 4

A C 2

B C 5

B D 10

C D 3

5
From To Weight

C E 8

D E 7

Step 1: Given Graph Representation

We start with the following edge list:

Where ∞ (infinity) means there's no direct edge.

Step 2: Applying Floyd-Warshall Algorithm

We systematically check if using an intermediate node provides a shorter path.

Iteration 1 (Using A as an Intermediate)

 No updates since A does not provide new paths.

6
Iteration 2 (Using B as an Intermediate)
 No updates since B does not provide new paths.

Iteration 3 (Using C as an Intermediate)

 A → D: Updated from ∞ to 5 via A → C → D = 2 + 3 = 5
 A → E: Updated from ∞ to 10 via A → C → E = 2 + 8 = 10
 B → D: Updated from 10 to 8 via B → C → D = 5 + 3 = 8
 B → E: Updated from ∞ to 13 via B → C → E = 5 + 8 = 13

Iteration 4 (Using D as an Intermediate)

 No updates since D does not provide new paths.

Iteration 5 (Using E as an Intermediate)

 No updates since E does not provide new paths.

Step 3: Final Shortest Path Matrix

After running the algorithm, we get the following corrected shortest path distances:

Python Code for Floyd-Warshall Algorithm:

python

7
Copy code
INF = float('inf') # Define infinity

# Adjacency matrix for the graph

graph = [
[0, 4, 2, INF, INF], # A → A, B, C, D, E
[INF, 0, 5, 10, INF], # B → A, B, C, D, E
[INF, INF, 0, 3, 8], # C → A, B, C, D, E
[INF, INF, INF, 0, 7], # D → A, B, C, D, E
[INF, INF, INF, INF, 0]# E → A, B, C, D, E
]

def floyd_warshall(graph):
V = len(graph) # Number of vertices
dist = [row[:] for row in graph] # Copy of the input graph

# Floyd-Warshall Algorithm
for k in range(V): # Intermediate node
for i in range(V): # Source node
for j in range(V): # Destination node
# Update dist[i][j] if a shorter path is found via node k
if dist[i][k] != INF and dist[k][j] != INF:
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

return dist

# Compute shortest paths

shortest_paths = floyd_warshall(graph)

# Print the final shortest path matrix

print("Shortest path matrix:")
for row in shortest_paths:
print(row)

Explanation of the Code:

1. Graph Representation:
o The graph is represented as an adjacency list, where each node points to a list of
tuples. Each tuple consists of a neighboring node and the weight (cost) of the edge
to that neighbor.
2. Distance Matrix Initialization:
o A dictionary dist is initialized with float('inf') to represent infinity for all
pairs of nodes. Then, for each edge in the graph, the distance is set to the weight
of the edge.
3. Relaxation:
o The core of the Floyd-Warshall algorithm is nested loops that update the distance
matrix. For each intermediate node k, for each pair of nodes i and j, the algorithm
checks if going from i to j through k gives a shorter path. If so, it updates
dist[i][j].
4. Output:
o The final distance matrix dist contains the shortest path distances between all
pairs of vertices.

8
Example Output:
mathematica
Copy code
Shortest distances between all pairs of nodes:
Distance from A to A: 0
Distance from A to B: 4
Distance from A to C: 2
Distance from A to D: 5
Distance from A to E: 10
Distance from B to A: inf
Distance from B to B: 0
Distance from B to C: 5
Distance from B to D: 8
Distance from B to E: 13
Distance from C to A: inf
Distance from C to B: inf
Distance from C to C: 0
Distance from C to D: 3
Distance from C to E: 8
Distance from D to A: inf
Distance from D to B: inf
Distance from D to C: inf
Distance from D to D: 0
Distance from D to E: 7
Distance from E to A: inf
Distance from E to B: inf
Distance from E to C: inf
Distance from E to D: inf
Distance from E to E: 0

Step-by-Step Execution:

1. Initialization: We start by setting the distance between each pair of nodes to infinity,
except for the diagonal (i.e., distance from a node to itself) which is 0. The graph's edge
weights are then added to the distance matrix.

css
Copy code
dist = {
'A': {'A': 0, 'B': 4, 'C': 2, 'D': inf, 'E': inf},
'B': {'A': inf, 'B': 0, 'C': 5, 'D': 10, 'E': inf},
'C': {'A': inf, 'B': inf, 'C': 0, 'D': 3, 'E': 8},
'D': {'A': inf, 'B': inf, 'C': inf, 'D': 0, 'E': 7},
'E': {'A': inf, 'B': inf, 'C': inf, 'D': inf, 'E': 0}
}

2. First Iteration (k = A): We update the distances by checking paths through A. For
example, we check if the distance from B to C via A is shorter than the current known
distance. If so, we update it.
3. Subsequent Iterations: We repeat this process for all intermediate nodes B, C, D, and E,
updating the shortest distances between all pairs of nodes.

9
 4. Final Output: The final distance matrix represents the shortest paths between all pairs of
vertices, even if there were negative weight edges (though no negative weight cycles in
this example).

Conclusion:

The Floyd-Warshall algorithm is an effective method for solving the all-pairs shortest path
problem in graphs with both positive and negative edge weights. It is particularly useful when
you need the shortest paths between all pairs of vertices, and it works efficiently for smaller
graphs. However, it has a time complexity of O(V3), which may not scale well for large graphs.

10