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

[K. Sun]

Thanks a lot. It works! I modify the code as follows and it runs
at fast as matlab. By numpy's convention, the input and output
are all ndarrays. 'route' has to be a (1xN) matrix to produce a
square matrix in 'route + route.T'.

def floyd( dis ):
     '''Floyd-Wallshall algorithm for shortest path
        
     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.mat( dis[k, :] )
         dis = np.minimum( dis, route + route.T )
         
    return np.array( dis )

* josef.pktd at gmail.com <josef.pktd at gmail.com> [2010-11-06 15:46:17 -0400]:

>On Sat, Nov 6, 2010 at 3:28 PM, K. Sun <sunk.cs at gmail.com> wrote:
>> 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, :] )
>
>I think your kron just does broadcasting, if you use
>
>route = dis[k:k+1, :]
>
>(I expect) you get the same results, and it would save one intermediary array
>
>>         dis = np.minimum( dis, route + route.T )
>
>Otherwise, I don't see much that I would speed up (without
>understanding the algorithm)
>
>Josef
>>
>>     return dis
>> _______________________________________________
>> NumPy-Discussion mailing list
>> NumPy-Discussion at scipy.org
>> http://mail.scipy.org/mailman/listinfo/numpy-discussion
>>
>_______________________________________________
>NumPy-Discussion mailing list
>NumPy-Discussion at scipy.org
>http://mail.scipy.org/mailman/listinfo/numpy-discussion

-- 
Ke Sun, Research Assistant
Viper Group, Computer Vision and Multimedia Lab
University of Geneva, Switzerland
Tel: +41 (0)22 379 0176    Fax: +41 (0)22 379 0250