Hi, On Wednesday 29 June 2005 10:05, Duncan Coutts wrote: > On Tue, 2005-06-28 at 12:11 +0300, Radu Grigore wrote: > > On 6/27/05, Arjun Guha <[EMAIL PROTECTED]> wrote: > > > It's the all-pairs > > > shortest paths data for a map of the Hyde Park area of Chicago (no real > > > reason, really). > > > > I wonder: is there really no way to do Floyd-Warshall in Haskell? > > Indeed I understand from a colleague who implemented an all-pairs > shortest paths algorithm in Haskell over the weekend for a map of the > Hyde Park area of Chicago (no real reason, really!), that it takes about > 0.1 seconds to execute (if you compile with -O), which is well within > the 5 second limit...
you can just use dijkstra from the fgl (http://www.haskell.org/ghc/docs/latest/html/libraries/fgl/Data.Graph.Inductive.Query.SP.html) for the paths you are interested. We used it *a lot* and we didn't have any performance problems. There is really no need to precompute all-pairs shortest path! Cheers, Stefan -- Stefan Wehr Web: http://www.stefanwehr.de PGP: Key is available from pgp.mit.edu, ID 0B9F5CE4 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe