graphs floyd warshall Algorithm
The Floyd-Warshall Algorithm is a classic dynamic programming algorithm that is widely used for solving the all-pairs shortest path problem in graph theory. This problem involves finding the shortest path between all pairs of vertices in a weighted graph (with either positive or negative edge weights). The algorithm works by considering each vertex in the graph as an intermediate point between other pairs of vertices and subsequently updating the shortest path between each pair if a shorter path is found through the intermediate vertex. The algorithm is popular due to its simplicity, efficiency, and ability to handle graphs with negative edge weights, provided there are no negative cycles.
One of the main strengths of the Floyd-Warshall Algorithm is its ability to efficiently compute the shortest path between all pairs of vertices in a graph in O(n^3) time complexity, where n is the number of vertices in the graph. This makes it particularly suitable for dense graphs, where the number of edges is relatively large in comparison to the number of vertices. Additionally, the algorithm can be easily extended to not only compute the shortest path distances but also to reconstruct the actual paths themselves. The algorithm's ease of implementation, versatility, and widespread applicability have made it a staple in the field of computer science and an essential tool for solving complex graph problems.
# floyd_warshall.py
"""
The problem is to find the shortest distance between all pairs of vertices in a weighted directed graph that can
have negative edge weights.
"""
def _print_dist(dist, v):
print("\nThe shortest path matrix using Floyd Warshall algorithm\n")
for i in range(v):
for j in range(v):
if dist[i][j] != float("inf"):
print(int(dist[i][j]), end="\t")
else:
print("INF", end="\t")
print()
def floyd_warshall(graph, v):
"""
:param graph: 2D array calculated from weight[edge[i, j]]
:type graph: List[List[float]]
:param v: number of vertices
:type v: int
:return: shortest distance between all vertex pairs
distance[u][v] will contain the shortest distance from vertex u to v.
1. For all edges from v to n, distance[i][j] = weight(edge(i, j)).
3. The algorithm then performs distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j]) for each
possible pair i, j of vertices.
4. The above is repeated for each vertex k in the graph.
5. Whenever distance[i][j] is given a new minimum value, next vertex[i][j] is updated to the next vertex[i][k].
"""
dist = [[float("inf") for _ in range(v)] for _ in range(v)]
for i in range(v):
for j in range(v):
dist[i][j] = graph[i][j]
# check vertex k against all other vertices (i, j)
for k in range(v):
# looping through rows of graph array
for i in range(v):
# looping through columns of graph array
for j in range(v):
if (
dist[i][k] != float("inf")
and dist[k][j] != float("inf")
and dist[i][k] + dist[k][j] < dist[i][j]
):
dist[i][j] = dist[i][k] + dist[k][j]
_print_dist(dist, v)
return dist, v
if __name__ == "__main__":
v = int(input("Enter number of vertices: "))
e = int(input("Enter number of edges: "))
graph = [[float("inf") for i in range(v)] for j in range(v)]
for i in range(v):
graph[i][i] = 0.0
# src and dst are indices that must be within the array size graph[e][v]
# failure to follow this will result in an error
for i in range(e):
print("\nEdge ", i + 1)
src = int(input("Enter source:"))
dst = int(input("Enter destination:"))
weight = float(input("Enter weight:"))
graph[src][dst] = weight
floyd_warshall(graph, v)
# Example Input
# Enter number of vertices: 3
# Enter number of edges: 2
# # generated graph from vertex and edge inputs
# [[inf, inf, inf], [inf, inf, inf], [inf, inf, inf]]
# [[0.0, inf, inf], [inf, 0.0, inf], [inf, inf, 0.0]]
# specify source, destination and weight for edge #1
# Edge 1
# Enter source:1
# Enter destination:2
# Enter weight:2
# specify source, destination and weight for edge #2
# Edge 2
# Enter source:2
# Enter destination:1
# Enter weight:1
# # Expected Output from the vertice, edge and src, dst, weight inputs!!
# 0 INF INF
# INF 0 2
# INF 1 0
