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

dijkstra-core.clj

(ns dijkstra.core)

(def initial-node {:score Integer/MAX_VALUE :route [] :dead? false})

(defn make-initial-state [edges start-node]
  (-> (zipmap (keys edges) (repeat initial-node))
      (assoc-in [start-node :score] 0)
      (assoc-in [start-node :route] [start-node])))

(defn live-nodes [state] 
  (remove
   #(:dead? (val %))
   state))

(defn find-current-source-node [state]
  (key (min-key #(:score (val %))
                 (live-nodes state))))

(defn update-node-score [state edge]
  (let [target-node (key edge)
        target-score (get-in state [target-node :score])
        source-score (get-in state [(find-current-node state) :score])
        source-route (get-in state [(find-current-node state) :route])
        trial-score (+ source-score (val edge))]
    
    (if (< trial-score target-score)
      (-> state
          (assoc-in [target-node :score] trial-score)
          (assoc-in [target-node :route] (conj source-route (key edge))))
      state)))

(defn apply-current-node [state]
  (let [current-node (find-current-node state)]
    (-> (reduce update-node-score 
                state (edges current-node))
        (assoc-in [current-node :dead?] true))))

(defn shortest-path [edges start-node end-node]
  (let [initial-state (make-initial-state edges start-node)
        final-state (last (take-while #(not (get-in % [end :dead?]))
                                      (iterate apply-current-node initial-state)))]
    (select-keys (final-state end-node)
                 [:score :route])))


;; so finally we can do:

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

(shortest-path edges :A :E)

;; which gives:
;; {:route [:A :C :F :E], :score 20}