floydwarshall 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 param graph 2d array calculated from weightedgei j type graph listlistfloat param v number of vertices type v int return shortest distance between all vertex pairs distanceuv will contain the shortest distance from vertex u to v 1 for all edges from v to n distanceij weightedgei j 3 the algorithm then performs distanceij mindistanceij distanceik distancekj for each possible pair i j of vertices 4 the above is repeated for each vertex k in the graph 5 whenever distanceij is given a new minimum value next vertexij is updated to the next vertexik check vertex k against all other vertices i j looping through rows of graph array looping through columns of graph array src and dst are indices that must be within the array size graphev failure to follow this will result in an error 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 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 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 check vertex k against all other vertices i j looping through rows of graph array looping through columns of graph array src and dst are indices that must be within the array size graph e v failure to follow this will result in an error 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
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):
    

    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]

            
    for k in range(v):
        
        for i in range(v):
            
            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

        
        
    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)