Ch-Assignment3-FloydWarshall

def floyd_warshall(graph):
    n = len(graph)
    # all distances are set to infinity at starting
    dist = [[float('inf')] * n for _ in range(n)]

    # diagonal elements set to 0
    for i in range(n):
        dist[i][i] = 0

    for u in range(n):
        for v in range(n):
            if u != v and graph[u][v] != float('inf'):
                dist[u][v] = graph[u][v]

    # They iterate through all possible vertices k, i, and j to consider if there is a
    # shorter path from vertex i to vertex j through vertex k

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    return dist

# Input-driven code
if __name__ == "__main__":
    num_vertices = int(input("Enter the number of vertices: "))
    Infinity = float('inf')
    graph = [[Infinity] * num_vertices for _ in range(num_vertices)]

    for i in range(num_vertices):
        for j in range(num_vertices):
            weight_input = input(f"Enter the weight from vertex {i+1} to vertex {j+1}: ")
            if weight_input.lower() == 'inf':
                graph[i][j] = Infinity
            else:
                graph[i][j] = float(weight_input)

    result = floyd_warshall(graph)
    for row in result:
        print(row)