Re: All pairs shortest paths
- To: mathgroup at smc.vnet.net
- Subject: [mg111404] Re: All pairs shortest paths
- From: Thomas Dowling <thomasgdowling at gmail.com>
- Date: Sat, 31 Jul 2010 02:40:14 -0400 (EDT)
Hello, I am not an expert here by any means, but there is such a command in the Combinatorica package: Needs["Combinatorica`"] ?AllPairsShortestPath As you are probably aware, the Combinatorica package is poorly documented compared with other parts of Mathematica. However, the function is described in detail in Sriram Pemmaraju & Stephen Skiena "Computational Discrete Mathematics. Combinatorics and Graph Theory with Mathematica", pp 330 - 333. Can you post an example of what you require? Tom Dowling On Fri, Jul 30, 2010 at 11:57 AM, Jon Harrop <usenet at ffconsultancy.com>wrote: > "Murta" <rodrigomurtax at gmail.com> wrote in message > news:i2jq2j$gr8$1 at smc.vnet.net... > > Try the Graph Utilities Package. There are some commands that can > > help. > > > > GraphDistance[g,start,end] give the distance from vertex i to vertex j > > in the graph g > > GraphPath[g,start,end] find a shortest path between vertices start and > > end in graph g > > GraphDistanceMatrix[g] give a matrix in which the (i,j)\[Null]^th > > entry is the length of a shortest path in g between vertices i and j > > GraphDistanceMatrix[g,Parent] return a three-dimensional matrix in > > which the (1,i,j)\[Null]^th entry is the length of a shortest path > > from i to j and the (2,i,j)\[Null]^th entry is the predecessor of j in > > a shortest path from i to j. > > Sure, but none of those actually implement what I need. The last one > returns > a data structure that can be used to compose the information I need but I'd > have to do the rest of the computation myself and it would run like a dog > if > written in Mathematica. > > Does Mathematica really not provide a built-in function to compute > all-pairs > shortest paths? > > Cheers, > Jon. > > >