[Haskell-cafe] Implementation of the Floyd-Warshall algorithm

[Sebastian Sylvan]

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))
                                                           ^^^^ typo

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))


/S

-- 
Sebastian Sylvan
+46(0)736-818655
UIN: 44640862