Re: All pairs shortest paths

• To: mathgroup at smc.vnet.net
• Subject: [mg111401] Re: All pairs shortest paths
• From: "Jon Harrop" <usenet at ffconsultancy.com>
• Date: Sat, 31 Jul 2010 02:39:41 -0400 (EDT)
• References: <i2eaij\$q7d\$1@smc.vnet.net> <i2jq2j\$gr8\$1@smc.vnet.net>

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

The documentation for the Graph Utilities package does actually give the
following code to compute the all pairs shortest paths from the output of
the GraphDistanceMatrix function:

Drop[FixedPointList[prd[[i, #]] &, j], -1] // Reverse

Although this code works on the trivial example they provide it does not
produce useful answers when applied to the more complicated graph given in
the previous example because the vertices are referred to via an unknown
mapping rather than by name. The best solution seems to be to convert the
graph represented as a list of rules into an adjacency matrix before
computing the all pairs shortest paths. For a 1005x1005 sparse graph on this
8-core, that takes 12.7s and requires ~1Gb of RAM.

Cheers,
Jon.

```

• Prev by Date: Re: AxesLabel parallel to 3D axes?
• Next by Date: Re: All pairs shortest paths
• Previous by thread: Re: All pairs shortest paths
• Next by thread: Re: All pairs shortest paths