File Exchange

image thumbnail

Vectorized Floyd-Warshall

version 1.0.0.0 (1.49 KB) by Dustin Arendt
Vectorized (fast) implementation of the Floyd-Warshall all pairs shortest path algorithm.

13 Downloads

Updated 07 Nov 2009

View License

The Floyd-Warshall algorithm computes the all pairs shortest path matrix for a given adjacency matrix. The algorithm is O(n^3), and in most implementations you will see 3 nested for loops. This is very inefficient in Matlab, so in this version the two inner loops are vectorized (and as a result, it runs much faster).

Make sure that your input matrix is initialized properly -- A(i,j) = Inf if i and j are not neighbors.

Cite As

Dustin Arendt (2021). Vectorized Floyd-Warshall (https://www.mathworks.com/matlabcentral/fileexchange/25776-vectorized-floyd-warshall), MATLAB Central File Exchange. Retrieved .

Comments and Ratings (8)

lowland44

lowland44

Carlos Rodriguez

muneeba murtaza

it is not working.
i m providing an adjacency matrix but it is giving an all 0 matrix as output.

Chris Oates

I'm certainly not an expert on this, but my understanding is that it is not possible to vectorise the Warshall algorithm since none of the calculations are performed in parallel - each depends on the former.

Having compared this algorithm's output to the unvectorised version, I believe this vectorised version gives incorrect answers.

Gerloi

great job. How can I get the whole path (way, vertexes)? I would like to use the vertexes.

Matlab2010

nice :)

Hongxun JIANG

it is really fast.

MATLAB Release Compatibility
Created with R2009b
Compatible with any release
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!