442 PurelyFunctional.tv Newsletter

00 Dijkstra's Algorithm.md

Dijkstra's Algorithm

Write a function to calculate the shortest path between two nodes in a graph using Dijkstra's Algorithm. The graph is directional and is represented as a map. The keys are pairs of nodes and the value is the cost to traverse the edge between them, from the first node to the second node. If a pair of nodes does not exist in the map, it means that there is no edge between them.

Example graph

(def graph {[:a :b] 1
            [:a :c] 2
            [:c :a] 4})

Your function should return a path, consisting of a sequence of the names of the nodes to follow, including the starting end ending nodes.

Example

(shortest-path graph :c :b) ;=> [:c :a :b]
(shortest-path graph :a :a) ;=> [:a]
(shortest-path graph :a :b) ;=> [:a :b]
(shortest-path graph :b :c) ;=> nil (because no path exists)

For a description of the algorithm, see the wikipedia page or any textbook on algorithms.

Please submit your solutions as comments on this gist.

To subscribe: https://purelyfunctional.tv/newsletter/

I convert the original "graph" input into a nested map. The cost-map is a map of a terminal node key to a vector path of nodes + cost. So the cost is accessed with peek, and the path is accessed with pop. I also keep the unvisited nodes (a set) under a special ::unvisited key in the same cost-map. A more conventional Clojure approach might use a more nested structure with explicit keys for the different kinds of information. Example of my cost-map state: {:b [:c :b 5] :c [:c 0] ::unvisited #{:a :b :d}}.

I was partially inspired by this blog post: http://loganlinn.com/blog/2013/04/22/dijkstras-algorithm-in-clojure/ But I have made a lot of changes so any bugs are my fault.

(defn best-unvisited-path [cost-map]
  (let [unvisited (::unvisited cost-map)]
    (pop (reduce-kv (fn [best k v]
                      (if (and (contains? unvisited k) (< (peek v) (peek best)))
                        v
                        best))
                    [Long/MAX_VALUE]
                    cost-map))))

(defn update-costs [g node cost-map]
  (let [node-cost (peek (cost-map node))
        node-path (pop (cost-map node))
        unvisited (disj (::unvisited cost-map) node)]
    (reduce-kv (fn [cm nbr nbr-step]
                 (if-not (contains? unvisited nbr)
                   cm
                   (let [new-cost (+ node-cost nbr-step)
                         nbr-path-cost (get cm nbr [Long/MAX_VALUE])]
                     (if (< new-cost (peek nbr-path-cost))
                       (assoc cm nbr (conj node-path nbr new-cost))
                       cm))))
               (assoc cost-map ::unvisited unvisited)
               (get g node))))


(defn shortest-path [path-map start end]
  (let [g (reduce-kv assoc-in {} path-map)]
    (loop [cost-map {start [start 0] ::unvisited (into #{} cat (keys path-map))}]
      (let [best-path (best-unvisited-path cost-map)
            node (peek best-path)]
        (cond (nil? node) nil
              (= node end) best-path
              :else (recur (update-costs g node cost-map)))))))

In case that is useful to others, here is the wikipedia example, which is both non-trivial and easy to verify visually:

(def wikipedia-example {[:1 :2] 7
                        [:1 :6] 14
                        [:1 :3] 9

                        [:2 :1] 7
                        [:2 :3] 10
                        [:2 :4] 15

                        [:3 :1] 9
                        [:3 :2] 10
                        [:3 :6] 2
                        [:3 :4] 11

                        [:4 :2] 15
                        [:4 :3] 11
                        [:4 :5] 6

                        [:5 :4] 6
                        [:5 :6] 9

                        [:6 :1] 14
                        [:6 :3] 2
                        [:6 :5] 9})

(shortest-path wikipedia-example :1 :5) ;;=> (:1 :3 :6 :5)
(shortest-path wikipedia-example :5 :4) ;;=> (:5 :4)
(shortest-path wikipedia-example :5 :3) ;;=> (:5 :6 :3)
(shortest-path wikipedia-example :3 :5) ;;=> (:3 :6 :5)
(shortest-path wikipedia-example :2 :6) ;;=> (:2 :3 :6)

(defn nodes [graph]
  (->> graph keys (apply concat) set))

(defn neighbors [node graph]
  (->> graph keys
       (filter #(= node (first %)))
       (map last) set))

(defn init [nodes start]
  (let [distances
        (-> (zipmap nodes (repeat Long/MAX_VALUE))
            (conj [start 0])),
        breadcrumbs
        (-> (zipmap nodes (repeat nil)))]
    {:distances distances
     :breadcrumbs breadcrumbs}))

(defn update-stats [stats neighbors from graph unvisited]
  (let [from-dist (get-in stats [:distances from])]
    (->> unvisited
         (filter neighbors)
         (reduce (fn [{:keys [distances breadcrumbs] :as stats} 
                      kand]
                   (let [kdist (+ from-dist 
                                  (graph [from kand]))
                         stats' (if (< kdist (distances kand))
                                  (-> stats 
                                      (assoc-in [:distances kand] kdist)
                                      (assoc-in [:breadcrumbs kand] from))
                                  stats)]
                     stats'))
                 stats))))

(defn gen-path [{:keys [breadcrumbs]} from]
  (let [path (fn step [path from]
                    (if-not from
                      path
                      (recur (conj path from) (get breadcrumbs from) )))]
    (path nil from)))


(defn best-node [stats unvisited]
  (->> (select-keys (:distances stats) unvisited)
       (reduce (fn [[min _ :as sel] [node dist]]
                 (if (< dist min)
                   [dist node]
                   sel))
               [Long/MAX_VALUE nil])
       second))

(defn shortest-path [graph start dest]
  (loop [current start
         unvisited (disj (nodes graph) start)
         stats (init unvisited start)]
    (let [nbrs (neighbors current graph)]
      (cond 
        (not current) 
        nil
        (not-any? unvisited (conj nbrs dest))
        (gen-path stats dest)
        :else 
        (let [stats' (update-stats stats nbrs current graph unvisited)
              current' (best-node  stats' unvisited) ]
          (recur current' 
                 (disj unvisited current')
                 stats'))))))