# Floyd-Warshall Algorithm in Python: Shortest Path Between Cities

The Floyd-Warshall algorithm is a renowned technique for finding the shortest paths between all pairs of nodes in a weighted graph or network. We can solve complex routing problems and optimize various processes by using this algorithm. In this article, we’ll explore the underlying principles of the Floyd-Warshall algorithm and its implementation in Python, along with a practical case study illustrating its application in finding the shortest routes between Indian cities.

Recommended: Connected Health: Exploring IoT Solutions for Healthcare Transformation

Recommended: Levenshtein Distance in Python: Troubleshooting Installation Errors on Windows

## Understanding the Floyd-Warshall Algorithm

The Floyd-Warshall algorithm is a dynamic programming approach that finds the shortest paths between all pairs of vertices in a weighted graph. It operates by iteratively updating a distance matrix, considering all possible intermediate vertices. The algorithm has a time complexity of O(n^3), where n is the number of vertices, making it efficient for solving the all-pairs shortest path problem.

## Implementing the Floyd-Warshall Algorithm in Python

The Python implementation of the Floyd-Warshall algorithm utilizes nested loops to iterate through all possible vertices and update the distance matrix accordingly.

The key steps involve initializing the distance matrix with the given edge weights, then iterating through each vertex as a potential intermediate node, updating the distance matrix if a shorter path is found.

```import matplotlib.pyplot as plt
import numpy as np

# Number of vertices in the graph
V = 4

# Define infinity as a large enough value. This value will be used
# for vertices not connected to each other
INF = 99999

# Solves all pair shortest path via Floyd Warshall Algorithm
def floydWarshall(graph):
""" dist[][] will be the output matrix that will finally have the shortest
distances between every pair of vertices """
""" initializing the solution matrix same as input graph matrix
OR we can say that the initial values of shortest distances
are based on shortest paths considering no intermediate vertex """
dist = list(map(lambda i: list(map(lambda j: j, i)), graph))

""" Add all vertices one by one to the set of intermediate
vertices.
---> Before start of an iteration, we have shortest distances
between all pairs of vertices such that the shortest
distances consider only the vertices in the set
{0, 1, 2, .. k-1} as intermediate vertices.
----> After the end of an iteration, vertex no. k is added
to the set of intermediate vertices and the set becomes {0, 1, 2, .. k} """
for k in range(V):

# pick all vertices as source one by one
for i in range(V):

# Pick all vertices as destination for the
# above picked source
for j in range(V):

# If vertex k is on the shortest path from
# i to j, then update the value of dist[i][j]
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
printSolution(dist)
plotGraph(graph, dist)

# A utility function to print the solution
def printSolution(dist):
print("Following matrix shows the shortest distances between every pair of vertices")
for i in range(V):
for j in range(V):
if(dist[i][j] == INF):
print("%7s" % ("INF"), end=" ")
else:
print("%7d\t" % (dist[i][j]), end=" ")
if j == V-1:
print("")

# A utility function to plot the graph and highlight the shortest paths
def plotGraph(graph, dist):
plt.figure(figsize=(8, 6))
G = np.array(graph)
np.fill_diagonal(G, 0)
plt.imshow(G, cmap='Greys', interpolation='nearest')
for i in range(V):
for j in range(V):
if dist[i][j] != graph[i][j] and graph[i][j] != INF:
plt.text(j, i, str(graph[i][j]), horizontalalignment='center', verticalalignment='center', fontdict={'color':'red'})
if dist[i][j] != INF:
plt.text(j, i, str(dist[i][j]), horizontalalignment='center', verticalalignment='center', fontdict={'color':'blue'})
plt.title("Graph with Shortest Paths (Red: Original, Blue: Shortest)")
plt.xlabel("Vertices")
plt.ylabel("Vertices")
plt.xticks(np.arange(V))
plt.yticks(np.arange(V))
plt.gca().invert_yaxis()
plt.colorbar(label="Edge Weight")
plt.grid(True, linestyle='--', linewidth=0.5)
plt.show()

# Driver program to test the above program
# Let us create the following weighted graph
"""
10
(0)------->(3)
|         /|\
5 |          |
|          | 1
\|/         |
(1)------->(2)
3           """
graph = [[0, 5, INF, 10],
[INF, 0, 3, INF],
[INF, INF, 0,   1],
[INF, INF, INF, 0]
]
# Print the solution and plot the graph
floydWarshall(graph)

```

The solution is visualized using the matplotlib library, highlighting the original and shortest path weights. Let us look at the output for the same.

## Case Study: Finding Shortest Paths Between Indian Cities

Let us now consider a case where we need to find the shortest distance between cities. We have three cities which are Mumbai, Delhi, and Bangalore.

Let’s assume that-

1. Mumbai is connected to Delhi with a distance of 10 units.
2. Mumbai is connected to Bangalore with a distance of 15 units.
3. Bangalore is connected to Delhi with a distance of 5 units.

We need to find the shortest distance. Let us look at the code.

```import numpy as np
import matplotlib.pyplot as plt

# Number of cities in the network
num_cities = 3

# Define infinity as a large enough value. This value will be used
# for cities not connected to each other
INF = 99999

# Function to find the shortest paths between all pairs of cities
def find_shortest_paths(distances):
""" dist[][] will be the output matrix that will finally have the shortest
distances between every pair of cities """
""" initializing the solution matrix same as input distances matrix
OR we can say that the initial values of shortest distances
are based on shortest paths considering no intermediate city """
dist = np.copy(distances)

""" Add all cities one by one to the set of intermediate
cities.
---> Before start of an iteration, we have shortest distances
between all pairs of cities such that the shortest
distances consider only the cities in the set
{0, 1, 2, .. k-1} as intermediate cities.
----> After the end of an iteration, city no. k is added
to the set of intermediate cities and the set becomes {0, 1, 2, .. k} """
for k in range(num_cities):
for i in range(num_cities):
for j in range(num_cities):
# If city k is on the shortest path from
# city i to city j, then update the value of dist[i][j]
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
return dist

# Function to plot the network of cities and roads
def plot_city_network(distances, city_names):
plt.figure(figsize=(8, 6))
plt.title("Network of Indian Cities")
for i in range(num_cities):
for j in range(num_cities):
if distances[i][j] != INF:
plt.plot([i, j], [j, i], 'k--', lw=0.5)
plt.text(i, j, str(distances[i][j]), horizontalalignment='center', verticalalignment='center')
plt.xticks(range(num_cities), city_names)
plt.yticks(range(num_cities), city_names)
plt.xlabel("Cities")
plt.ylabel("Cities")
plt.grid(True)
plt.gca().invert_yaxis()
plt.show()

# Function to print the shortest paths between all pairs of cities
def print_shortest_paths(dist, city_names):
print("Shortest distances between every pair of cities:")
for i in range(num_cities):
for j in range(num_cities):
if dist[i][j] == INF:
print("Shortest distance from city {} to city {} is INF".format(city_names[i], city_names[j]))
else:
print("Shortest distance from city {} to city {} is {}".format(city_names[i], city_names[j], dist[i][j]))

# Define the distances between cities in the network
distances = np.array([[0, 10, 15],
[INF, 0, 5],
[INF, INF, 0]])

# Define the names of Indian cities
city_names = ['Mumbai', 'Delhi', 'Bangalore']

# Find the shortest paths between all pairs of cities
shortest_paths = find_shortest_paths(distances)

# Print the shortest paths
print_shortest_paths(shortest_paths, city_names)

# Plot the network of cities and roads
plot_city_network(distances, city_names)

```

Let us look at the output.

## Conclusion

Now you know Floyd Warshall’s algorithm and how to use it to solve real-life problems. We also learned how to implement this concept in Python. How can the Floyd-Warshall algorithm be extended or modified to handle dynamic or time-varying networks, where the edge weights or connectivity may change over time?

Recommended: Delivery Route Optimization using Python: A Step-by-Step Guide

Recommended: Understanding the Capital Asset Pricing Model (CAPM)