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.