# Computing All Shortest Paths in Python

##### December 03, 2009

A research problem I'm working on involves Isomap, a method of dimensionality reduction that requires computing all shortest paths over relatively large graphs. In interpreted languages like Matlab this is often done through the use of the Floyd-Warshall algorithm, a simple $O(n^3)$ dynamic programming approach to computing all shortest paths. In the reference Isomap code this algorithm takes only three lines:

 1 2 3 for k=1:N D = min(D,repmat(D(:,k),[1 N])+repmat(D(k,:),[N 1])); end

The benefits of Floyd-Warshall are two-fold for languages like Matlab. The first is that the implementation is short and simple. The second is that the implementation can employ a number of linear algebra primitives that are highly optimized in languages like Matlab. In the code snippet above the repmat, addition, and min operations are all implemented as low-level highly optimized library calls. This means that Floyd-Warshall, despite the non-optimal runtime, is often the fastest Matlab approach to computing all shortest paths even on reasonably large problem sizes.

In my work, I've reimplemented Isomap in Python (which will soon appear in my algorithms gallery). My implementation of Floyd-Warshall uses NumPy for access to similarly optimized low-level linear algebra routines. Here's my original Python code snippet: