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))
 
    # Adding the vertices individually
    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)

Feedback