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

[josef.pktd at gmail.com]

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
>