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.

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