[Numpy-discussion] Optimize Floyd-Wallshall algorithm with Numpy

[K. Sun]

Hello,

I wrote the following code with numpy to implement the Floyd-Wallshall
algorithm to compute the pair-wise shortest path in a undirected weighted
graph. It is really slow when N ~ 10k, while the same implementation in
matlab is much faster. I am sorry I don't want to run it again to 
present some accurate comparison. Is there any suggestions to optimize
this code without destroying the elegant coding style of python?
Thank you very much.

def floyd( dis ):
     '''
     dis is the pair-wise distance matrix.
     return and update dis as the shortest path matrix w_{ij}.'''

     N = dis.shape[0]
     for k in range( N ):
         route = np.kron( np.ones( (N, 1) ), dis[k, :] )
         dis = np.minimum( dis, route + route.T )

     return dis