Floyd-Warshall

def FloydWarshall(g):
    distancia = [[INF] * len(g) for i in range(len(g))]
    predecesor = [[(-1,-1)] * len(g) for i in range(len(g))]
    for i in range(len(g)):
        distancia[i][i] = 0
        for u,v in g[i]:
            distancia[i][u] = v
            predecesor[i][u] = (i,v)
    for k in range(len(g)):
        for i in range(len(g)):
            for j in range(len(g)):
                if distancia[i][j] > distancia[i][k] + distancia[k][j]:
                    distancia[i][j] = distancia[i][k] + distancia[k][j]
                    predecesor[i][j] = (k,distancia[k][j])
    return distancia,predecesor

print(FloydWarshall(g))

def hacerRecorridosFloydWarshall(g):
    d, p = FloydWarshall(g)
    recorrido = [[]]
    for u in range(len(p)):
        recorrido += [[]]
        for v in range(len(p)):
            if p[u][v][0] > -1:
                recorrido[u] += [(p[u][v][0],v,p[u][v][1])]
    return recorrido

hacerRecorridosFloydWarshall(g)