dijkstra.clj

(ns dijkstra.core)

(defn unvisited-neighbors
  "Returns unvisited node's neighbors"
  [graph node unvisited] (select-keys (get graph node) unvisited))

(defn update-costs
  "Returns costs updated with any shorter paths found to curr's unvisited
   neighbors by using curr's shortest path"
  [g costs curr unvisited]
  (let [curr-cost (costs curr)]
    (reduce
     (fn [result [nbr nbr-cost]]
       (update result nbr (fn [x] (min x (+ curr-cost nbr-cost)))))
     costs
     (unvisited-neighbors g curr unvisited))))


(defn dijkstra
  "Returns a mapping of nodes to minimum cost from src using Dijkstra algorithm.
   Graph is a mapping of nodes to map of neighboring nodes and associated cost."
  [g src]
  (let [initial-costs (zipmap (keys g) (repeat ##Inf))
        initial-unvisited (into #{} (keys g))]
    (loop [costs (assoc initial-costs src 0)
           curr src
           unvisited (disj initial-unvisited src)]
      (if (empty? unvisited)
        costs
        (let [costs' (update-costs g costs curr unvisited)
              curr' (first (sort-by costs' unvisited)) ;; costs' is a map therefore it behaves as a function
              unvisited' (disj unvisited curr') ;; remove curr' from unvisited
              ]
          (recur costs' curr' unvisited'))))))

(def g {:a {:b 2 :c 3}
        :c {}
        :b {:d 3}
        :d {:e 1 :f 4}
        :f {:h 5 :a 2}})

(dijkstra g :f)