""" Floyd warshall in numpy and standard implementation """
from numpy import * 
inf = float('inf')
graph = [
    [0, 3, 8, inf, -4], 
    [inf, 0, inf, 1, 7], 
    [inf, 4, 0, inf, inf], 
    [2, inf, -5, 0, inf], 
    [inf, inf, inf, 6, 0]
]


def make_matrix(file, n):
    graph = [[inf for i in range(n)] for i in range(n)]
    with open(file) as f:
        for l in f:
           (i, j, w) = l.split() 
           graph[int(i)-1][int(j)-1] = int(w)
    return graph


def floyd_warshall(graph):
    n = len(graph)
    D = graph
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if i==j:
                    D[i][j] = 0
                else:
                    D[i][j] = min(D[i][j], D[i][k] + D[k][j])
    return D


def fastfloyd(D):
    _, n = D.shape
    for k in range(n):
        i2k = reshape(D[k, :], (1, n))
        k2j = reshape(D[:, k], (n, 1))
        D = minimum(D, i2k + k2j)
    return D.min() if not any(D.diagonal() < 0) else None


def get_min_dist(D):
    if negative_cost_cycle(D):
        return "Negative cost cycle"
    return min(i for d in D for i in d)


def negative_cost_cycle(D):
    n = len(D)
    for i in range(n):
        if D[i][i] < 0:
            return True
    return False


if __name__ == "__main__":
    print(get_min_dist(floyd_warshall(graph)))
    n = 1000
    gr = make_matrix("g1.txt", n)
    D = floyd_warshall(gr)
    print(fastfloyd(array(gr)))
    print(get_min_dist(D))
    print(D)
