Floyd-Warshall Algorithm.

Floyd-Warshall use case.


In Computer Sciense the Floyd-Warshall Algorithm is an algorithm for finding the shortest paths between all the pairs of vertices in a weighted graph. It is also called as Roy-Floyd algorithm, Roy-Warshall algorithm or WFI algorithm. A single execution of the algorithm is sufficient to find the lengths of the shortest paths between all pairs of vertices.

Floyd-Warshall Algorithm.



It works for the directed and undirected weighted graphs, but it does not work for the graphs with negative cycles. The Floyd-Warshall algorithm is a good example of dynamic programming, which breaks the problem down into several smaller subproblems and then combines the answers to those subproblems to solve the initial problem.


Floyd-Warshall Algorithm Python code:



# number of vertices
nV = 4
# Define infinity as a large number
INF = 99999

# main function
def FloydWarshall(G):
    distance = list(map(lambda i: list(map(lambda j: j, i)), G))

    # Adding vertices
    for k in range(nV):
        for i in range(nV):
            for j in range(nV):
                distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])
    print_solution(distance)


# Print the solution
def print_solution(distance):
    for i in range(nV):
        for j in range(nV):
            if(distance[i][j] == INF):
                print("INF", end=" ")
            else:
                print(distance[i][j], end="  ")
        print(" ")


G = [[0, 5, INF, 10],
         [INF, 0, 3, INF],
         [INF, INF, 0,   1],
         [INF, INF, INF, 0]
         ]

print ("Shortest distances between every pair of vertices:\n")

FloydWarshall(G)

Floyd-Warshall output.



See also related topics: