[Date Index] [Thread Index] [Author Index]

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.
>
>
>