# 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
assert(N == w.shape) # 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