Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Brisfunctional dojo code implementing dijkstra's algorithm 29-05-2012
(ns dijkstra.core)
(def edges {:A {:F 14 :C 9 :B 7}
:B {:A 7 :C 10 :D 15}
:C {:A 9 :B 10 :D 11 :F 2}
:D {:B 15 :C 11 :E 6}
:E {:D 6 :F 9}
:F {:A 14 :C 2 :E 9}})
(def inf Integer/MAX_VALUE)
(def initial-state {:A {:score 0 :route [:A] :dead? false}
:B {:score inf :route [] :dead? false}
:C {:score inf :route [] :dead? false}
:D {:score inf :route [] :dead? false}
:E {:score inf :route [] :dead? false}
:F {:score inf :route [] :dead? false}
(def start :A)
(def end :E)
(defn live-nodes [state]
#(not (:dead? (val %)))
(defn find-current-node [state]
(key (first
(sort-by #(:score (val %))
(live-nodes state)))))
(defn update-node-score [state edge]
(let [target-key [(key edge) :score]
target-score (get-in state target-key)
source-score (get-in state [(find-current-node state) :score])]
(assoc-in state target-key (min target-score (+ source-score (val edge))))))
(update-node-score initial-state (first {:B 7}))
(defn apply-current-node [state]
(let [current-node (find-current-node state)]
state (edges current-node))
[current-node :dead?] true)))
(last (take-while #(not (get-in % [end :dead?])) (iterate apply-current-node initial-state)))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment