Recommended: Levenshtein Distance in Python: Troubleshooting Installation Errors on Windows<\/a><\/em><\/strong><\/p>\n\n\n\n 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.<\/em><\/p>\n<\/blockquote>\n\n\n\n The Python implementation of the Floyd-Warshall algorithm utilizes nested loops to iterate through all possible vertices and update the distance matrix accordingly. <\/p>\n\n\n\n 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. <\/p>\n\n\n The solution is visualized using the matplotlib library, highlighting the original and shortest path weights. Let us look at the output for the same.<\/p>\n\n\n\n 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.<\/p>\n\n\n\n Let’s assume that-<\/p>\n\n\n\n We need to find the shortest distance. Let us look at the code.<\/p>\n\n\n Let us look at the output.<\/p>\n\n\n\n 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? <\/p>\n\n\n\n Recommended: Delivery Route Optimization using Python: A Step-by-Step Guide<\/a><\/em><\/strong><\/p>\n\n\n\nUnderstanding the Floyd-Warshall Algorithm<\/h2>\n\n\n\n
\n
Implementing the Floyd-Warshall Algorithm in Python<\/h2>\n\n\n\n
\nimport matplotlib.pyplot as plt\nimport numpy as np\n\n# Number of vertices in the graph\nV = 4\n\n# Define infinity as a large enough value. This value will be used\n# for vertices not connected to each other\nINF = 99999\n\n# Solves all pair shortest path via Floyd Warshall Algorithm\ndef floydWarshall(graph):\n """ dist[][] will be the output matrix that will finally have the shortest\n distances between every pair of vertices """\n """ initializing the solution matrix same as input graph matrix\n OR we can say that the initial values of shortest distances\n are based on shortest paths considering no intermediate vertex """\n dist = list(map(lambda i: list(map(lambda j: j, i)), graph))\n \n """ Add all vertices one by one to the set of intermediate\n vertices.\n ---> Before start of an iteration, we have shortest distances\n between all pairs of vertices such that the shortest\n distances consider only the vertices in the set\n {0, 1, 2, .. k-1} as intermediate vertices.\n ----> After the end of an iteration, vertex no. k is added\n to the set of intermediate vertices and the set becomes {0, 1, 2, .. k} """\n for k in range(V):\n \n # pick all vertices as source one by one\n for i in range(V):\n \n # Pick all vertices as destination for the\n # above picked source\n for j in range(V):\n \n # If vertex k is on the shortest path from\n # i to j, then update the value of dist[i][j]\n dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])\n printSolution(dist)\n plotGraph(graph, dist)\n\n# A utility function to print the solution\ndef printSolution(dist):\n print("Following matrix shows the shortest distances between every pair of vertices")\n for i in range(V):\n for j in range(V):\n if(dist[i][j] == INF):\n print("%7s" % ("INF"), end=" ")\n else:\n print("%7d\\t" % (dist[i][j]), end=" ")\n if j == V-1:\n print("")\n\n# A utility function to plot the graph and highlight the shortest paths\ndef plotGraph(graph, dist):\n plt.figure(figsize=(8, 6))\n G = np.array(graph)\n np.fill_diagonal(G, 0)\n plt.imshow(G, cmap='Greys', interpolation='nearest')\n for i in range(V):\n for j in range(V):\n if dist[i][j] != graph[i][j] and graph[i][j] != INF:\n plt.text(j, i, str(graph[i][j]), horizontalalignment='center', verticalalignment='center', fontdict={'color':'red'})\n if dist[i][j] != INF:\n plt.text(j, i, str(dist[i][j]), horizontalalignment='center', verticalalignment='center', fontdict={'color':'blue'})\n plt.title("Graph with Shortest Paths (Red: Original, Blue: Shortest)")\n plt.xlabel("Vertices")\n plt.ylabel("Vertices")\n plt.xticks(np.arange(V))\n plt.yticks(np.arange(V))\n plt.gca().invert_yaxis()\n plt.colorbar(label="Edge Weight")\n plt.grid(True, linestyle='--', linewidth=0.5)\n plt.show()\n\n# Driver program to test the above program\n# Let us create the following weighted graph\n"""\n 10\n (0)------->(3)\n | \/|\\\n 5 | |\n | | 1\n \\|\/ |\n (1)------->(2)\n 3 """\ngraph = [[0, 5, INF, 10],\n [INF, 0, 3, INF],\n [INF, INF, 0, 1],\n [INF, INF, INF, 0]\n ]\n# Print the solution and plot the graph\nfloydWarshall(graph)\n\n<\/pre><\/div>\n\n\n![\"Floyd](\"https:\/\/www.askpython.com\/wp-content\/uploads\/2024\/04\/Floyd-Warshall-Output.png\")
Case Study: Finding Shortest Paths Between Indian Cities<\/h2>\n\n\n\n
\n
\nimport numpy as np\nimport matplotlib.pyplot as plt\n\n# Number of cities in the network\nnum_cities = 3\n\n# Define infinity as a large enough value. This value will be used\n# for cities not connected to each other\nINF = 99999\n\n# Function to find the shortest paths between all pairs of cities\ndef find_shortest_paths(distances):\n """ dist[][] will be the output matrix that will finally have the shortest\n distances between every pair of cities """\n """ initializing the solution matrix same as input distances matrix\n OR we can say that the initial values of shortest distances\n are based on shortest paths considering no intermediate city """\n dist = np.copy(distances)\n \n """ Add all cities one by one to the set of intermediate\n cities.\n ---> Before start of an iteration, we have shortest distances\n between all pairs of cities such that the shortest\n distances consider only the cities in the set\n {0, 1, 2, .. k-1} as intermediate cities.\n ----> After the end of an iteration, city no. k is added\n to the set of intermediate cities and the set becomes {0, 1, 2, .. k} """\n for k in range(num_cities):\n for i in range(num_cities):\n for j in range(num_cities):\n # If city k is on the shortest path from\n # city i to city j, then update the value of dist[i][j]\n dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])\n return dist\n\n# Function to plot the network of cities and roads\ndef plot_city_network(distances, city_names):\n plt.figure(figsize=(8, 6))\n plt.title("Network of Indian Cities")\n for i in range(num_cities):\n for j in range(num_cities):\n if distances[i][j] != INF:\n plt.plot([i, j], [j, i], 'k--', lw=0.5)\n plt.text(i, j, str(distances[i][j]), horizontalalignment='center', verticalalignment='center')\n plt.xticks(range(num_cities), city_names)\n plt.yticks(range(num_cities), city_names)\n plt.xlabel("Cities")\n plt.ylabel("Cities")\n plt.grid(True)\n plt.gca().invert_yaxis()\n plt.show()\n\n# Function to print the shortest paths between all pairs of cities\ndef print_shortest_paths(dist, city_names):\n print("Shortest distances between every pair of cities:")\n for i in range(num_cities):\n for j in range(num_cities):\n if dist[i][j] == INF:\n print("Shortest distance from city {} to city {} is INF".format(city_names[i], city_names[j]))\n else:\n print("Shortest distance from city {} to city {} is {}".format(city_names[i], city_names[j], dist[i][j]))\n\n# Define the distances between cities in the network\ndistances = np.array([[0, 10, 15],\n [INF, 0, 5],\n [INF, INF, 0]])\n\n# Define the names of Indian cities\ncity_names = ['Mumbai', 'Delhi', 'Bangalore']\n\n# Find the shortest paths between all pairs of cities\nshortest_paths = find_shortest_paths(distances)\n\n# Print the shortest paths\nprint_shortest_paths(shortest_paths, city_names)\n\n# Plot the network of cities and roads\nplot_city_network(distances, city_names)\n\n<\/pre><\/div>\n\n\n![\"Floyd](\"https:\/\/www.askpython.com\/wp-content\/uploads\/2024\/04\/Floyd-Warshall-case-study-output.png\")
Conclusion<\/h2>\n\n\n\n