dijkstra.clj

(ns dijkstra.core
  (:require [clojure.data.priority-map :refer [priority-map]]))

(def ^:private ^:const infinity ##Inf)

(defmacro infinity? [x] `(= ~x ##Inf))

(defn- construct-path [m start end]
  (loop [weight 0
         path (list)
         v end]
    (if (= v start)
      {:path (cons v path) :weight weight}
      (let [[w cost] (get m v)]
        (recur (+ weight cost) (cons v path) w)))))

(defn dijkstra
  ([vertices neighbour-fn weight-fn]
   (->> (map #(dijkstra vertices % neighbour-fn weight-fn) vertices)
        (reduce into)
        set
        seq))
  ([vertices start neighbour-fn weight-fn]
   (filter some? (map #(dijkstra vertices start % neighbour-fn weight-fn) vertices)))
  ([vertices start end neighbour-fn weight-fn]
   (loop [paths (transient {})
          xs (-> (priority-map)
                 (into (map vector vertices (repeat infinity)))
                 (assoc start 0))]
     (when-let [[v s-v-cost] (peek xs)]
       (cond (infinity? s-v-cost) nil   ; only unreachable vertices are left
             (= v end) (construct-path (persistent! paths) start end)
             :else (let [[updated-paths ys]
                         (reduce (fn [[paths xs :as acc] w]
                                   (if-let [s-w-cost (get xs w)] ; may have already removed w from xs
                                     (let [v-w-cost (weight-fn v w)
                                           s-v-w-cost (+ s-v-cost v-w-cost)]
                                       (if (< s-v-w-cost s-w-cost)
                                         [(assoc! paths w [v v-w-cost]) (assoc xs w s-v-w-cost)]
                                         acc))
                                     acc))
                                 [paths (pop xs)]
                                 (neighbour-fn v))]
                     (recur updated-paths ys)))))))


(def g {:t {:x 10 :y 7}
        :x {:t 20 :y 8}
        :y {:x 5}
        :s {:a 7 :b 2 :c 3}
        :a {:s 7 :b 3 :d 4}
        :b {:s 2 :a 3 :d 4 :h 1}
        :d {:a 4 :b 4 :f 5}
        :g {:e 2 :h 2}
        :h {:b 1 :f 3 :g 2}
        :f {:d 5 :h 3}
        :c {:s 3 :l 2}
        :l {:c 2 :i 4 :j 4}
        :i {:l 4 :j 6 :k 4}
        :j {:l 4 :i 6 :k 4}
        :k {:i 4 :j 4 :e 5}
        :e {:g 2 :k 5}})

(def result (dijkstra (keys g)
                      (fn get-neighbours [node] (keys (get g node)))
                      (fn get-edge-weight [& nodes] (get-in g nodes)) ; (constantly 1) 
                      :s
                      :e))