Graph distances, how can I speed it up?
Brian Kelley
bkelley at wi.mit.edu
Mon Jun 3 17:02:50 CEST 2002
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
More information about the Python-list
mailing list