MathGroup Archive 2010

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

Search the Archive

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





  • Prev by Date: Re: Mathematica- Use a previous equation into the function Function
  • Next by Date: Re: Cannot load example data
  • Previous by thread: Re: discretized Laplacian or linear inverse problem with extremely
  • Next by thread: Re: All pairs shortest paths