[Haskell-cafe] Implementation of the Floyd-Warshall algorithm
sylvan at student.chalmers.se
Fri Jul 28 06:57:40 EDT 2006
On 7/28/06, Sebastian Sylvan <sylvan at student.chalmers.se> wrote:
> On 7/28/06, frederic at ka-ge-ro.org <frederic at ka-ge-ro.org> wrote:
> > Hi,
> > I'm new to Haskell (yet I am very familiar with Lisp and OCaml), and
> > I am trying to implement the Floyd-Warshall algorithm (finding the
> > minimal distance between two nodes in a weighted graph). For an input
> > graph with 101 nodes, the obvious C version takes 0.01 s on my machine.
> > My first totally functional implementation in Haskell took 6s... for
> > a graph with 10 edges. (This version considered that a graph is given
> > as its adjacency matrix, which is represented as a 2-uple in
> > ([k], k -> k -> Double)). [I do not show my code, as I am ashamed of it :-S]
> > My first question is: what would an (efficient?) version of the algorithm
> > using this representation would look like ? Is it possible to do without
> > ressorting to the ST monad ?
> Dynamic programming is actually quite neat in Haskell.
> You can express it quite directly using arrays.
> arr = array (1,n) [ (k, foo k) | k <- [1..n]]
> foo k = ...
> now, foo would reference arr in some way, it it should probably
> contain some base case for k=1. So you basically just let "foo k" be
> the actual algorithm in question, and then arr!x (x = n most likely)
> would be your final result.
> Laziness is really neat here you see. You can define the array 'arr'
> such that its elements actually reference 'arr' in their definition
> (no need to obfuscate the algorithm with bottom-up construction like
> in imperative languages).
> IIRC Floyd Warshall would be a 3 dimensional array whose k=0 elements
> would simply be the distance matrix. Something like (untested!):
> fw :: Array Int Double -> Int -> Int -> Double
> fw dist i j = d!(n,i,j)
> where (_,(_,n)) = bounds dist -- find n, assum vertices are 1..n
> d = array ((0,1,1),(n,n,n)) [((k,i,j), foo k i j) | k <-
> [0..n], i <- [1..n], j <- [1..n]]
> foo 0 i j = dist!(i,j) -- base case, just the weighted edges
> foo k i j = min (d!(k-1,i,j)) (d!(k-1,k,k) + d!(k-1,k,j))
Bah, spotted a typo, it's (of course):
foo k i j = min (d!(k-1,i,j)) (d!(k-1,i,k) + d!(k-1,k,j))
More information about the Haskell-Cafe