Created on 2012-11-8 @author: Pandara ''' import sys def floyd(l, n): ''' l: l[i][j] = distace of i and j if <i, j> in E else sys.maxint k: sum of point ''' d = l[:] route = [([''] * n) for i in range(n)] for i in range(n): for j in range(n): if d[i][j]: route[i][j] = str(i + 1) + " " + str(j + 1) for k in range(n): for i in range(n): for j in range(n): if d[i][j] > d[i][k] + d[k][j]: d[i][j] = d[i][k] + d[k][j] route[i][j] = route[i][k] + " " + route[k][j][2:] return d, route if __name__ == "__main__": n = 3 l = [[0, 2, 9], [8, 0, 6], [1, sys.maxint, 0]] d, route = floyd(l, n) for i in d: for j in i: print j, print "" for i in route: for j in i: print "[" + j + "],", print ""