import numpy as np


def floyd(d, p):
    for k in range(0, len(d)):
        for i in range(0, len(d)):
            for j in range(0, len(d)):
                if d[i][k] + d[k][j] < d[i][j]:
                    d[i][j] = d[i][k] + d[k][j]
                    p[i][j] = p[i][k]
    return d, p


p = np.array([[1, 2, 3, 4, 5, 6, 7, 8],
              [1, 2, 3, 4, 5, 6, 7, 8],
              [1, 2, 3, 4, 5, 6, 7, 8],
              [1, 2, 3, 4, 5, 6, 7, 8],
              [1, 2, 3, 4, 5, 6, 7, 8],
              [1, 2, 3, 4, 5, 6, 7, 8],
              [1, 2, 3, 4, 5, 6, 7, 8],
              [1, 2, 3, 4, 5, 6, 7, 8]])

d = np.array([[0, 9, np.inf, 3, np.inf, np.inf, np.inf, np.inf],
              [9, 0, 2, np.inf, 7, np.inf, np.inf, np.inf],
              [np.inf, 2, 0, 2, 4, 8, 6, np.inf],
              [3, np.inf, 2, 0, np.inf, np.inf, 5, np.inf],
              [np.inf, 7, 4, np.inf, 0, 10, np.inf, np.inf],
              [np.inf, np.inf, 8, np.inf, 10, 0, 7, np.inf],
              [np.inf, np.inf, 6, 5, np.inf, 7, 0, np.inf],
              [np.inf, np.inf, np.inf, np.inf, 9, 12, 10, 0]])


print floyd(d, p)