[Date Index] [Thread Index] [Author Index]
Re: All pairs shortest paths
"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.