Code covered by the BSD License  

Highlights from
Shortest path (all pair shortest path)

1.0

1.0 | 3 ratings Rate this file 27 Downloads (last 30 days) File Size: 1.48 KB File ID: #23462

Shortest path (all pair shortest path)

by

 

28 Mar 2009 (Updated )

Finds all pair shortest path.

| Watch this File

File Information
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)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (3)
24 Jul 2012 Ule

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!

14 Nov 2011 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)

24 Jan 2011 Ule

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

Updates
30 Mar 2009

Corrected discription

Contact us