The Floyd-Warshall-Roy algorithm is an algorithm for finding shortest paths in a weighted, directed graph. It allows for negative edge weights and detects a negative weight cycle if one exists. Assuming that there are no negative weight cycles, a single execution of the FWR algorithm will find the shortest paths between all pairs of vertices.

This algorithm is an example of dynamic programming, which allows one to break the computation down to simpler steps using some sort of recursive procedure. If then this is a -time algorithm. For comparison, the Bellman-Ford algorithm has complexity , which is -time for “dense” graphs. However, Bellman-Ford only yields the shortest paths eminating from a *single* vertex. To achieve comparable output, we would need to iterate Bellman-Ford over *all* vertices, which would be an -time algorithm for “dense” graphs. Except for “sparse” graphs, Floyd-Warshall-Roy is better than an interated implementation of Bellman-Ford.

Here is a Sage implementation

def floyd_warshall_roy(A): """ Shortest paths INPUT: A - weighted adjacency matrix OUTPUT dist - a matrix of distances of shortest paths paths - a matrix of shortest paths EXAMPLES: sage: A = matrix([[0,1,2,3],[0,0,2,1],[20,10,0,3],[11,12,13,0]]); A sage: floyd_warshall_roy(A) ([[0, 1, 2, 2], [12, 0, 2, 1], [14, 10, 0, 3], [11, 12, 13, 0]], [-1 1 2 1] [ 3 -1 2 3] [ 3 -1 -1 3] [-1 -1 -1 -1]) sage: A = matrix([[0,1,2,4],[0,0,2,1],[0,0,0,5],[0,0,0,0]]) sage: floyd_warshall_roy(A) ([[0, 1, 2, 2], [+Infinity, 0, 2, 1], [+Infinity, +Infinity, 0, 5], [+Infinity, +Infinity, +Infinity, 0]], [-1 1 2 1] [-1 -1 2 3] [-1 -1 -1 3] [-1 -1 -1 -1]) sage: A = matrix([[0,1,2,3],[0,0,2,1],[-5,0,0,3],[1,0,1,0]]); A sage: floyd_warshall_roy(A) Traceback (click to the left of this block for traceback) ... ValueError: A negative edge weight cycle exists. sage: A = matrix([[0,1,2,3],[0,0,2,1],[-1/2,0,0,3],[1,0,1,0]]); A sage: floyd_warshall_roy(A) ([[0, 1, 2, 2], [3/2, 0, 2, 1], [-1/2, 1/2, 0, 3/2], [1/2, 3/2, 1, 0]], [-1 1 2 1] [ 2 -1 2 3] [-1 0 -1 1] [ 2 2 -1 -1]) """ G = Graph(A, format="weighted_adjacency_matrix") V = G.vertices() E = [(e[0],e[1]) for e in G.edges()] n = len(V) dist = [[0]*n for i in range(n)] paths = [[-1]*n for i in range(n)] # initialization step for i in range(n): for j in range(n): if (i,j) in E: paths[i][j] = j if i == j: dist[i][j] = 0 elif A[i][j] != 0: dist[i][j] = A[i][j] else: dist[i][j] = infinity # iteratively finding the shortest path for j in range(n): for i in range(n): if i != j: for k in range(n): if k != j: if dist[i][k]>dist[i][j]+dist[j][k]: paths[i][k] = V[j] dist[i][k] = min(dist[i][k], dist[i][j] +dist[j][k]) for i in range(n): if dist[i][i] < 0: raise ValueError, "A negative edge weight cycle exists." return dist, matrix(paths)

Hi David,

I get some syntax errors, first at

elif A[i][j]0:

then at

for k in range(n):

I tinkered around with no luck. I’m using version 4.3 if that helps!

Thanks,

Kathy

Thanks for noticing that. I think there is a bug in how wordpress displays “