## Posts Tagged ‘path’

### 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)
,('d','e',10)]
print \$ shortestPath 'a' 'e' g == "ace"
```

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