Skip to content

Instantly share code, notes, and snippets.

@rileylev
Created April 20, 2019 14:10
Show Gist options
  • Save rileylev/7ad84dec75a9a00d53f2d70de637027c to your computer and use it in GitHub Desktop.
Save rileylev/7ad84dec75a9a00d53f2d70de637027c to your computer and use it in GitHub Desktop.
Dijkstra's algorithm in clojure
(defprotocol WEIGHTED_GRAPH
(nodes [graph])
(neighbors [graph node])
(weight [graph from to]))
(defn dijkstra
[start goal graph]
(let [nodes (nodes graph)
neighbors #(neighbors graph %)
weight #(weight graph %1 %2)]
(loop [dist (merge (into {} (for [x nodes] [x ##Inf]))
{start 0})
unseen (into (priority-map) tentative-dist)
visited? #{}
path {}]
(let [[best-unseen best-dist] (peek unseen)]
(if (or (= best-dist ##Inf) ; no path from start to goal
(visited? goal)
(empty? unseen))
(path goal)
(let [closer-nbrs (for [nbr (neighbors best-unseen)
:let [new-dist (+ best-dist
(weight best-unseen nbr))]
:when (< new-dist (dist nbr))]
[nbr new-dist])
closer-paths (for [[nbr _] closer-nbrs]
[nbr (conj (path best-unseen) nbr)])]
(recur (into dist closer-nbrs)
(into (pop unseen) closer-nbrs)
(conj visited? best-unseen)
(into path closer-paths))))))))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment