Python-powered perfection: Floyd-Warshall algorithm at your service.

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.
Floyd-Warshall Algorithm meme.

Python Knowledge Base: Make coding great again.
- Updated: 2024-07-23 by Andrey BRATUS, Senior Data Analyst.




    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.


  1. Floyd-Warshall Algorithm Python code:


  2. 
    # 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)
    

  3. Floyd-Warshall Algorithm code result:


  4. Floyd-Warshall output.



See also related topics: