MathGroup Archive 2010

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

Search the Archive

Re: All pairs shortest paths

  • To: mathgroup at
  • Subject: [mg111404] Re: All pairs shortest paths
  • From: Thomas Dowling <thomasgdowling at>
  • Date: Sat, 31 Jul 2010 02:40:14 -0400 (EDT)


I am not an expert here by any means, but there is such a command in the



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>wrote:

> "Murta" <rodrigomurtax at> wrote in message
> news:i2jq2j$gr8$1 at
> > 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.

  • Prev by Date: Re: All pairs shortest paths
  • Next by Date: Re: Surface integral on a 3D region
  • Previous by thread: Re: All pairs shortest paths
  • Next by thread: Strange use of time...