# # Floyd-Warshall algorithm in Python # # and a bit of testing code at the bottom... # def fw( graph2d, nnodes ): INF = float('inf') n = nnodes fwgraph = [] # build infinity graph for k in range(n+1): plane = [] for r in range(n): row = [] for c in range(n): col = INF row += [col] plane += [row] fwgraph += [plane] # fill in level "zero" of the fwgraph for r in range(n): for c in range(n): fwgraph[0][r][c] = graph2d[r][c] # Floyd-Warshall for k in range(1,n+1): for r in range(n): for c in range(n): fwgraph[k][r][c] = min( fwgraph[k-1][r][c], (fwgraph[k-1][r][k-1]+fwgraph[k-1][k-1][c]) ) return fwgraph if __name__ == "__main__": # traditional graph from ACM (and some CS60) slides... G = [ [1, 2, 14], [2, 3, 14], [3, 4, 14], [4, 1, 10], [1, 4, 100], [2, 4, 50]] nnodes = 4 nedges = 6 graph2d = [ [ float('inf') for c in range( nnodes ) ] for r in range( nnodes ) ] for edge in range(nedges): # read in edges src,dst,distance = G[edge] src -= 1 dst -= 1 graph2d[src][dst] = distance print "graph2d is", graph2d fwgraph = fw( graph2d, nnodes ) print "fwgraph is", fwgraph