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