# Floyd Warshall

The Floyd-Warshall algorithm is a computational procedure designed to determine the shortest path connecting all pairs of vertices within a weighted graph. It operates on dynamic programming principles, systematically computing and updating the optimal paths between vertices in the graph. Here’s an example implementation of Floyd Warshall algorithm:

Python

# Total number of vertices
vertices = 4

INF = 999

# implementing the floyd-warshall algorithm
def floyd_warshall(Graph):
distance = list(map(lambda a: list(map(lambda b: b, a)), Graph))

for k in range(vertices):
for a in range(vertices):
for b in range(vertices):
distance[a][b] = min(distance[a][b], distance[a][k] + distance[k][b])
solution(distance)

# Printing the desired solution
def solution(distance):
for a in range(vertices):
for b in range(vertices):
if(distance[a][b] == INF):
print("INF", end=" ")
else:
print(distance[a][b], end=" ")
print(" ")

Graph = [[0, 3, INF, 5],
[2, 0, INF, 4],
[INF, 1, 0, INF],
[INF, INF, 2, 0]]
floyd_warshall(Graph)

Previous
Next