create-graph.clj

(ns dijkstra.core)


(defn make-graph [] (atom {}))
(defn add-node [g node]
  (swap! g assoc node {}))

(defn add-edge [g src target]
  (swap! g update src #(assoc % target 1)))





(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 (make-graph))
(add-node g "paris")
(add-node g "rome")
(add-node g "prague")
(add-edge g "paris" "rome")
(add-edge g "rome" "prague")
(add-edge g "prague" "paris")

(dijkstra @g "paris")