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.
"""


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):
    """
    :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].
    """

    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]

            # check vertex k against all other vertices (i, j)
    for k in range(v):
        # looping through rows of graph array
        for i in range(v):
            # looping through columns of graph array
            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

        # src and dst are indices that must be within the array size graph[e][v]
        # failure to follow this will result in an error
    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)

    # 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
