Re: All pairs shortest paths
- To: mathgroup at smc.vnet.net
- Subject: [mg111447] Re: All pairs shortest paths
- From: Daniel Lichtblau <danl at wolfram.com>
- Date: Mon, 2 Aug 2010 07:02:23 -0400 (EDT)
- References: <i2eaij$q7d$1@smc.vnet.net> <i2jq2j$gr8$1@smc.vnet.net>
On Jul 31, 1:41 am, "Jon Harrop" <use... at ffconsultancy.com> wrote: > "Jon Harrop" <use... at ffconsultancy.com> wrote in message > > news:i2ub6h$jga$1 at smc.vnet.net... > > > Does Mathematica really not provide a built-in function to compute > > all-pairs > > shortest paths? > > FWIW, this is quite tricky so I have blogged a solution here: > > http://mathematicanews.blogspot.com/2010/07/all-pairs-shortest-paths.... > > Cheers, > Jon. I think parts of this are misleading. (1) "The all - pairs shortest paths algorithm from graph theory computes the shortest paths from every vertex in a graph to every other vertex." Correct, but let us clarify. The accepted definition is that it gives path lengths, and (depending on specifics of what you want) perhaps also path reconstruction information in the form of immediate predecessors. There is a reason for this (see below). Further information, which looks correct, may be found at the Wikipedia article below. http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm (2) "The algorithm used is called Floyd - Warshall and it takes O (n^3) time and O (n^2) space where n is the number of vertices in the graph." This is where things go wrong if you get careless. First, the graph may be sparse. In such cases the speed complexity is down to O(n^2*d) where d is some measure of degree (max, or average, say). For many large graphs in common usage this will be far better than O(n^3). Of similar importance is that best paths may reach O(n) in the number of vertices. Thus to provide the full paths as well as their lengths would make the problem O(n^3) both in speed and memory. Unless you absolutely need to have all paths fully specified, this is a huge loss of efficiency vs. the standard Floyd-Warshall result (where memory really is O(n^2)). (3) "Although Wolfram Research cheekily worked this example into the Numb3rs TV show, Mathematica does not actually provide a complete implementation of the algorithm required to obtain the shortest paths but, rather, is only able to return the path lengths and further information that can be used to derive the paths themselves." I checked on this. http://numb3rs.wolfram.com/413/#floyd_warshall_algorithm It is pretty likely that, for the (briefly) stated purpose, what is needed are the path lengths and not the paths themselves. I will add that the implementation in SparseArray`AllPairsShortestPath and GraphUtilities and the similar Combinatorica function do seem to provide what is required by the standard meaning of Floyd-Warshall. That "further information" is the key. (4) "Hopefully this program will help anyone else who wants to solve this problem using Mathematica." I had some difficulties. It is HTML so I could not cut/paste it, and was too small for me to read. I can imagine ways in which it might be provided in a more usable form. Daniel Lichtblau Wolfram Research