Posts Tagged ‘dijkstra’

Programming Praxis – Dijkstra’s Algorithm

January 4, 2011

In today’s Programming Praxis, our task is to implement Dijkstra’s shortest path algorithm. Let’s get started, shall we?

Some imports:

import Data.List
import qualified Data.List.Key as K
import Data.Map ((!), fromList, fromListWith, adjust, keys, Map)

In order make the rest of the algorithm simpler, we convert the list of edges to a map that lists all the neighbors of each vertex.

buildGraph :: Ord a => [(a, a, Float)] -> Map a [(a, Float)]
buildGraph g = fromListWith (++) $ g >>=
               \(a,b,d) -> [(a,[(b,d)]), (b,[(a,d)])]

The algorithm follows the usual steps, albeit in a functional rather than the typical procedural style: start by giving all non-source vertices an infinite distance, then go through all the vertices in order of their distance from the source, relaxing all their neighbors.

dijkstra :: Ord a => a -> Map a [(a, Float)] -> Map a (Float, Maybe a)
dijkstra source graph =
    f (fromList [(v, (if v == source then 0 else 1/0, Nothing)) 
                | v <- keys graph]) (keys graph) where
    f ds [] = ds
    f ds q  = f (foldr relax ds $ graph ! m) (delete m q) where
              m = K.minimum (fst . (ds !)) q
              relax (e,d) = adjust (min (fst (ds ! m) + d, Just m)) e

Getting the shortest path is then simply a matter of tracing the path from the endpoint to the beginning.

shortestPath :: Ord a => a -> a -> Map a [(a, Float)] -> [a]
shortestPath from to graph = reverse $ f to where
    f x = x : maybe [] f (snd $ dijkstra from graph ! x)

A test to see if everything is working properly:

main :: IO ()
main = do let g = buildGraph [('a','c',2), ('a','d',6), ('b','a',3)
                             ,('b','d',8), ('c','d',7), ('c','e',5)
          print $ shortestPath 'a' 'e' g == "ace"

As expected, the shortest route for the given graph is A-C-E.

Programming Praxis – The Sum Of Two Squares

January 5, 2010

In today’s Programming Praxis exercise we have to find all the ways a given number can be written as the sum of the squares of two other numbers. Let’s get started.

All we really have to do is to convert the four cases of Dijkstra’s algorithm (listed on the second page of the exercise) from English to Haskell, which is trivial. To avoid repeating ourselves, we pattern match on the result of the comparison between x*x + y*y and n instead of recalculating it three times.

squareSum :: Integer -> [(Integer, Integer)]
squareSum n = b (ceiling . sqrt $ fromIntegral n) 0 where
    b x y = if x < y then [] else case compare (x*x + y*y) n of
                LT -> b x (y + 1)
                EQ -> (x, y) : b (x - 1) (y + 1)
                GT -> b (x - 1) y

A quick test shows us that everything’s working correctly.

main :: IO ()
main = do print $ squareSum 50
          print $ squareSum 48612265
          print $ squareSum 999