Graph distances, how can I speed it up?

[Brian Kelley]

While a C or C++ implementation would be prefereable, there are more 
efficient algorithms for shortest distance between nodes. 
Floyd-Warshall comes to mind.  (I think Andrew Dalke helped me with this 
one a while ago just to give appropriate credit)

import Numeric
# Finds the all-pairs minimum distance between two points.
#
# Initial matrix must be a symmetric "weight" matrix w[i][j] where
# w[i][i] == 0 and w[i][j] is the direct distance between i and j.
# This is usually 1 but can be weighted for importance.
#
# Must have a symmetric matrix for this implementation

def floyd_warshall(w):
     assert(len(w.shape) == 2) # must be a 2D array
     N = w.shape[0]
     assert(N == w.shape[1]) # must be a square 2D array

     k = 0
     dold = w # destroys contents of w
     # (Use this if you don't want to destroy)
     #dold = Numeric.array(w)

     dnew = Numeric.zeros((N,N))

     for k in range(1, N):
         for i in range(N):
	    #  We can do this simplification because of symmetry
             for j in range(i+1, N):
		x = min(dold[i][j], dold[i][k] + dold[k][j])
                 dnew[i][j] = x
                 dnew[j][i] = x

         dnew, dold = dold, dnew
     return dold

Brian Kelley
Whitehead Institute for Biomedical Research