Clojure implementation of the A* path finding algorithm

astar.clj

;; This is the Wikipedia entry example encoded graph.
(def graph {:orig [{:a 1.5 :d 2} 0]
            :a    [{:orig 1.5 :b 2} 4]
            :b    [{:a 2 :c 3} 2]
            :c    [{:b 3 :dest 4} 4]
            :dest [{:c 4 :e 2} 0]
            :e    [{:dest 2 :d 3} 2]
            :d    [{:orig 2 :e 3} 4.5]})

(defn a* [graph orig dest]
  (letfn [(discover [node path visited]
            (let [walkable (first (graph node))
                  seen (map last (keys visited))]
              (reduce dissoc walkable (conj seen (last path)))))
          (walk [visited]
            (let [[[score node :as current] [path total-distance]] (first visited)]
              (if (= dest node)
                (conj path dest)
                (recur
                  (reduce-kv
                    (fn [m neighbour partial-distance]
                      (let [d (+ total-distance partial-distance)
                            score (+ d (last (graph neighbour)))]
                        (assoc m [score neighbour] [(conj path node) d])))
                    (dissoc visited current)
                    (discover node path visited))))))]
    (walk (sorted-map-by compare [0 orig] [[] 0]))))

(a* graph :orig :dest)
;; [:orig :d :e :dest]