File Exchange

image thumbnail

Shortest path (all pair shortest path)

version 1.1 (1.48 KB) by

Finds all pair shortest path.

1 Download

Updated

View License

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

Comments and Ratings (4)

VB

VB (view profile)

Hello, I am trying to understand where is Dijkstra used here, could anyone help me to translate the code a litlle bit? Thank you so much.
:)

Ule

Ule (view profile)

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

Ule

Ule (view profile)

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

Updates

1.1

Corrected discription

MATLAB Release
MATLAB 7.6 (R2008a)

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video