Asymptotic Analysis of Dijkstras in Haskell

Imagine you have a map of the US. You want to know the distances from Providence to all the other cities. We can turn that map into a network of cities and distances between them. In math and computer science, we call this a graph (and we refer to the cities as vertices or nodes). Our goal in this post is to using functional programming to find the shortest distances from Providence using Dijkstra's algorithm. It's going to get CS-heavy in the rest of the post so buckle up.

TLDR: Even though Haskell's Map and Set are $O(\log N)$^[1], I was able still get Dijkstra's in $O((V + E)\log V)$. I used the PSQueue library for my priority queue.

Let's first recall the structure of Dijkstra's algorithm. I've included pseudo code below with asymptotic analysis for each line. The idea is we have a frontier (Q) that keeps track of what we think the shortest path is, and we update it as we remove the closest city (and add it's neighbors). Dijkstra's overall runtime is $O((V + E) \log V)$ or $O(V \log V + E)$ using Fibonacci heaps.

We need a visited set so we don't re-explore cities that we've already gone to.

dijkstras(s,G)
     Q = Heap()                                          O(1)
     visited = set()                                     O(1)
     weights = map()                                     O(1)

     Q.put(s, 0)
     while !Q.empty                                      O(V)
             n,w = Q.pop_min()                           O(V * log V)
             weights[n] = w                              O(V * 1)
             visited.add(n)                              O(V * 1)
             for (w_m, m) in neighbors of n in G         O(E)
                     if m visited: skip                  O(E * 1)
                     Q.insert_or_decrease(m, w + w_m)    O(E * log V) O(E)

So now, the question is, can this be done in the same time complexity, and the answer is yes^[1]. I wrote two haskell functions, dijkstras which does the outside loop of taking a vertex off the queue, updating the frontier, the map of weights that we'll return, and the visited set. To update the frontier, we need to loop through all the edges connected to the vertex we just popped off. I made a function specifically for that which checks for containment in the visited set, and will either insert or decrease the priority of the node. Here's the code, with asymptotic analysis on the side. Anything with an exclamation point is asymptotically faster in the imperative version, but the overall runtime turns out to be the same.

type Node = String
-- adjacency list
type Graph = Map.Map Node [(Float, Node)]

dijkstras :: Graph -> Node -> Map.Map Node Float
dijkstras graph start = dijkstras_helper Set.empty (PSQ.singleton start 0) Map.empty
  where
    dijkstras_helper visited frontier weights = 
      case PSQ.minView frontier of                         -- O(V)
        Nothing -> weights                                 -- O(V * 1 / V)
        Just (binding, frontier') -> let                   -- O(V * 1)
            node = PSQ.key binding                         -- O(V * 1)
            w = PSQ.prio binding                           -- O(V * 1)
            edges = fromJust $ Map.lookup node graph       -- O(V * log V)!
            visited' = Set.insert node visited             -- O(V * log V)!
            weights' = Map.insert node w weights           -- O(V * log V)!
            frontier'' = foldr (update_keys visited' w) frontier' edges -- O(E * log V)
            in
            dijkstras_helper visited' frontier'' weights'   -- O(V * 1)

-- acts as the inner loop of dijkstras, goes through the adjacent nodes and updates the frontier
update_keys :: Set.Set Node -> Float -> (Float, Node) -> PSQ.PSQ Node Float -> PSQ.PSQ Node Float
update_keys visited w_0 (w, node) acc = 
  if Set.member node visited                               -- O(log V)!
  then acc                                                 -- O(1)
  else 
    case PSQ.lookup node acc of                            -- O(log V)!
      Nothing -> PSQ.insert node (w + w_0) acc             -- O(log V)
      Just p -> PSQ.adjust (\_ -> min p (w + w_0)) node acc-- O(log V)

the_us :: Graph
the_us = Map.fromList [
    ("Prov", [(2.0, "NY"), (1.0, "Boston"), (3.0, "Chester")]), 
    ("NY", [(2.7, "Boston"), (2.0, "Prov"), (5.0, "DC")]), 
    ("Boston", [(1.0, "Prov"), (2.5, "Chester")]),
    ("DC", [(5.0, "NY")]),
    ("Chester", [(3.0, "Prov"), (2.5, "Boston")])
    ]

main :: IO ()
main = do 
    putStrLn "Map of the US:"
    putStrLn $ show $ dijkstras the_us "Prov"