Code covered by the BSD License
Bharat Patel (view profile)
28 Mar 2009
30 Mar 2009)
Finds all pair shortest path.
Watch this File
Outperforms other algorithms in speed and memory requirement especially for large dataset.
%function [costs] = mdijkstra(A,C)
%A=square matrix (either adjacency or cost)
%if C=1 then A=adjacency matrix
% where, element(i,j)=1 when vertex v is directly connected with j
% else (i,j)=0
%if C=2 then A=cost matrix
% where, element (i,j) represents positive integer representing cost
% between vertex i and j
% Output: [costs]: calculated cost matrix
% Developed by: Bharat Patel
% Release date: 03/28/2009
Have to update my rating. As the other user I found examples of undirected graphs where the result of the algorithm does not return a symmetric matrix. There has to be a bug somewhere!
sometimes outputs wrong result for relatively large input adjacency matrices. I tried the following symmetric adjacency matrix and got an output that was not symmetric:
>> a = [1 1 0 0 0; 1 1 1 1 0; 0 1 1 0 0; 0 1 0 1 1; 0 0 0 1 1];
>> b = kron(a,a);
Works great, much faster than all the other implementations I've downloaded so far (2 seconds for 1000 vertices on my laptop). Thanks