Floyd-Warshall Algorithm in Python: Shortest Path Between Cities

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)

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)