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/

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