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

dijkstra-core.clj

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