Created
May 29, 2012 22:13
-
-
Save tcoupland/2831122 to your computer and use it in GitHub Desktop.
Brisfunctional dojo code implementing dijkstra's algorithm 29-05-2012
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
(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] | |
(filter | |
#(not (:dead? (val %))) | |
state)) | |
(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)] | |
(assoc-in | |
(reduce | |
update-node-score | |
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