Programming Praxis – Dijkstra’s Algorithm

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.

About these ads

Tags: , , , , , , , , ,

15 Responses to “Programming Praxis – Dijkstra’s Algorithm”

  1. egorzabelin Says:

    I wanted to ask is this code really work?
    I tried to run it on HaskellPlatform 2011.2.0.0 and got
    “Could not find module ‘Data.List.Key’. i just started to learn this language…what i should do to to fix this mistake.

    will be appreciate!!!!!!

  2. Remco Niemeijer Says:

    You’re missing the utility-ht package (http://hackage.haskell.org/package/utility-ht). If you have cabal installed, just type

    cabal install utility-ht

    at the command line. You can also do it manually, but it’s more laborious.

  3. egorzabelin Says:

    what if i have windows?

  4. egorzabelin Says:

    oh, know it works. grate!
    one more question – if i need to find the longest path, what i need to change in this code?

  5. Remco Niemeijer Says:

    You’ll need a different algorithm entirely. Finding the longest path is the same as finding the shortest path on a graph with negative weights. However, Dijkstra’s algorithm requires that the weights are positive, so it cannot be modified to calculate the longest path. Wikipedia has an algorithm you can use: http://en.wikipedia.org/wiki/Longest_path_problem

  6. egorzabelin Says:

    I think, i’ll use this algorithm, cause i just started to learn language.
    it’s doesn’t matter what algorithm to use for finding the longest path, so i will finish this exercise like you said – with negative weights.
    thank you!

  7. egorzabelin Says:

    one more thing. if i will use negative weight, i need to change data types. what will be better?

  8. egorzabelin Says:

    i’m asking, because when i put negative weights (

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

    the result path was ”.
    :(

  9. Remco Niemeijer Says:

    Like I said, the Dijkstra algorithm doesn’t work with negative weights, so you’ll have to use a different algorithm. There’s no change you can make to the code in this exercise that will make it correctly calculate the longest path.

  10. egorzabelin Says:

    ohh…understand :(

  11. egorzabelin Says:

    i know, that i can’t ask you, but if you will have some time – can you help me with this algorithm?
    will be appreciate, because i’am not sure that i will consult with it for the time i have

  12. Remco Niemeijer Says:

    As mentioned, the Wikipedia page has an algorithm in pseudocode. Just start by translating that into Haskell. You can use the data structure and buildgraph function from the exercise to create the graphs.

  13. Christian Says:

    Am I missing something, or you transform a directed graph in a connected graph, removing the directionality in the edges?
    In your example, the path from ‘e’ to ‘a’ should return empty list, but it returns ‘ace’ instead.

  14. Remco Niemeijer Says:

    @Christian: It appears I did. I reread the original exercise and it doesn’t explicitly state the graph is directed. The image is indeed a directed graph, but the original problem statement is about roads between cities, which typically are bidirectional. Apparently (It’s been a year and a half, so I don’t exactly remember my decisions) I chose to treat the graph as a connected one.

    • Christian Says:

      I see. I like the “very functional” :) way in which you wrote the dijkstra function. Could you provide a suggestion on how to extend it to the directed case?
      The algorithm does not work when building the graph via edges
      g >>= \(a,b,d) -> [(a,[(b,d)])]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: