public
Created — forked from mantree/dijkstra-core.clj

Brisfunctional dojo code implementing dijkstra's algorithm 29-05-2012

  • Download Gist
dijkstra-core.clj
Clojure
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
(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)))

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.