Instantly share code, notes, and snippets.

# ericnormand/00 Dijkstra's Algorithm.md

Created September 14, 2021 19:59
Show Gist options
• Save ericnormand/732246722ef3d632bb5c6aa391a8a899 to your computer and use it in GitHub Desktop.

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.

### miner commented Sep 17, 2021 • edited

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

### KingCode commented Sep 21, 2021 • edited

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

### KingCode commented Sep 24, 2021

```(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])),
(-> (zipmap nodes (repeat nil)))]
{:distances distances

(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)
stats)]
stats'))
stats))))

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