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

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.