simple python implemetation of Floyd-Warshall alghorithm

floydwarshall.py

def floydwarshall(graph):
    # simple python implemetation of Floyd-Warshall alghorithm
    # https://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm#Path_reconstruction
    # source: https://jlmedina123.wordpress.com/2014/05/17/floyd-warshall-algorithm-in-python/
    # author: J. Luis Medina
    dist = {}
    pred = {}
    for u in graph:
        dist[u] = {}
        pred[u] = {}
        for v in graph:
            dist[u][v] = 1000
            pred[u][v] = -1
        dist[u][u] = 0
        for neighbor in graph[u]:
            dist[u][neighbor] = graph[u][neighbor]
            pred[u][neighbor] = u

    for t in graph:
        # given dist u to v, check if path u - t - v is shorter
        for u in graph:
            for v in graph:
                newdist = dist[u][t] + dist[t][v]
                if newdist < dist[u][v]:
                    dist[u][v] = newdist
                    pred[u][v] = pred[t][v] # route new path through t
    return dist