depth first search

I compared two Python implementations for computing shortest paths in a previous post. This was all inspired by some Matlab code for computing Isomap that contained the following version of the Floyd-Warshall algorithm:

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

Of course, mirroring my Python comparison, I decided to recreate the Matlab version using outer products instead of repmat.

for k=1:N
    D = min(D, D(:,k) * D(k,:));
end

As with my Python comparison, the implementation using outer products was faster (31.6 seconds to 59.3 seconds). The time difference between approaches was again about 30 seconds, which is very similar to the previous Python comparison.

The Matlab code ran about 10 seconds faster than the corresponding Python code in both cases, though you should probably take that result with a grain of salt as I was not careful to control for a number of possible confounding factors between the two experiments.