shortest distance between all pairs of vertexes in a graph (floyd warshall algorithm)

FloydWarshallAlgorithm.py

from sys import stdin, stdout
INF = float('Inf')

def build_floyd_table(n, m):
    # initalize with all values to INF
    distance_table = [[INF]*n for i in range(n)]
    # set the diagonal values to 0
    for i in range(0, n):
        distance_table[i][i] = 0
    # all has been set, input the edges 
    # also build the distance table simultaneously 
    for i in range(m):
        u, v, r = [int(x) for x in stdin.readline().split()]
        # reduce 1 since we start from 0
        u -= 1
        v -= 1
        distance_table[u][v] = r
    
    # now run the algo
    # if d[i][j] > d[i][k] + d[k][j]:
    #       d[i][j] = d[i][k] + d[k][j]
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if distance_table[i][k] != INF and distance_table[k][j] != INF:
                    if distance_table[i][j] > distance_table[i][k] + distance_table[k][j]:
                        distance_table[i][j] = distance_table[i][k] + distance_table[k][j]
    return distance_table

def query(u, v, distance_table):
    return -1 if distance_table[u][v] == INF else distance_table[u][v]
    
if __name__ == '__main__':
    n, m = [int(x) for x in stdin.readline().split()]
    distance_table = build_floyd_table(n, m)
    q = int(stdin.readline())
    for i in range(q):
        u, v = [int(x)-1 for x in stdin.readline().split()]
        stdout.write(str(query(u, v, distance_table)) + '\n')