Shortest path (all pair shortest path)

Finds all pair shortest path.

Description

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

• MATLAB release: MATLAB 7.6 (R2008a)

[Ule]

Works great, much faster than all the other implementations I've downloaded so far (2 seconds for 1000 vertices on my laptop). Thanks

[Ali Dabirmoghaddam]

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);
>> mdijkstra(b,1)