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

### Highlights from "All Pairs Shortest Path" Graph Solver

3.88889
3.9 | 9 ratings Rate this file 15 Downloads (last 30 days) File Size: 2.96 KB File ID: #8808 Version: 1.0

# "All Pairs Shortest Path" Graph Solver

### Michael Kleder (view profile)

24 Oct 2005 (Updated )

Gives the shortest node-to-node distance along the edges of a graph for all node combinations.

File Information
Description

ALLSPATH - solve the All Pairs Shortest Path problem

Rapidly returns the shortest node-to-node distance along the edges of a graph, for all nodes in the graph.

USAGE: B = allspath(A)

A = input distance matrix between nodes

B = shortest path distance matrix between all nodes

Notes:
(1) For a graph with n nodes, A is an n-by-n distance matrix giving the distances between adjacent nodes. Since the distance from point i to point j is the same as the distance from point j to point i, A must be a symmetric matrix
(2) The distance from a node to itself can either be entered as zero or infinity. (Either will produce a correct result.) This means that the diagonal elements of the matrix A must all be either zero or infinity.
(3) The distance between nodes that are not adjacent to each other must be entered as either zero or infinity. (Either will produce a correct result.) This means that the (i,j) and (j,i) elements of A, where i and j are non-adjacent nodes, must all be either zero or infinity.
(4) If the input graph is not "connected," meaning that some nodes cannot be reached from other nodes no matter how many edges are traversed, then the distances between nodes that cannot be connected will be returned as infinite.
(5) Distances between a node and itself are returned as zero.
(6) This function codifies an original algorithm created by the author.
(7) No warranties; use at your own risk.
(8) Written by Michael Kleder, October 2005.

Acknowledgements

This file inspired Dijkstra's Minimum Cost Path Algorithm.

MATLAB release MATLAB 7.0.4 (R14SP2)
Tags for This File   Please login to tag files.
Comments and Ratings (16)
31 May 2015 Suchetana Gupta

### Suchetana Gupta (view profile)

Does this also return the exact path visited? Mine is a weighted network

Comment only
15 Nov 2012 Xuan Vinh Nguyen

### Xuan Vinh Nguyen (view profile)

I think Matlab now provides a similar function:
http://www.mathworks.com.au/help/bioinfo/ref/graphallshortestpaths.html

Comment only
22 Aug 2012 MRR

### MRR (view profile)

22 Sep 2011 srinadh

### srinadh (view profile)

awesome,simple to use

26 Jul 2011 srinadh

### srinadh (view profile)

Is there a way to find the path also along with the distance?

thanks

Comment only
21 Jan 2011 Ule

### Ule (view profile)

Works nice for small graphs (100 nodes), but if the graph becomes a bit larger (say, 500 nodes) it takes forever and effectively freezes my laptop...

23 May 2007 Joseph Kirk

Thank you for putting in the effort to update the file with the new example for those of us lacking the Statistics Toolbox. :)

However, I still had some difficulty testing it. References were made to variables 'a' and 'b' that did not exist. I was able to run the example when I added the following code after "% distance matrix:"

>> k=(1:10); a=k(ones(1,10),:); b=a';

21 May 2007 The Author

Thank you. PDIST does require the Statistics Toolbox, so I have removed it from the example and uploaded a replacement submission where the example does not use PDIST.

Comment only
18 May 2007 Joseph Kirk

The example didn't work for me...
??? Undefined function or method 'pdist' for input arguments of type 'double'.
Do I need a special toolbox for this?

Comment only
14 Apr 2007 John S

Works great for me, < 200-ish nodes. Thanks!

26 Oct 2006 David Leamer

What a beautifully compact algorithm! Works fast for up to about 200-250 nodes. For more than that it works but uses a lot of memory. This is really*great for smallish (about 200 nodes) investigational type problems that I'm working on right now.

16 Oct 2006 Dead Beat

Doesn't work, fails with a "??? Out of memory. Type HELP MEMORY for your options." even tho my graph has 600 nodes & I have 1GB of RAM!

29 Jun 2006 Kyaw Tun

It give out of memory error even though my graph has only 702 nodes. :-)

27 Apr 2006 giuseppe d

There are a limit whenever we have a large graph. Out of memory proble...
Somebody tried?
G

Comment only
26 Apr 2006 giuseppe d

But what happens it the graph is not undirected? I think it doesn't work...

Comment only
09 Dec 2005 LIU Jerry

It is indeed useful for my research!