Skip to content

Instantly share code, notes, and snippets.

@loganlinn

loganlinn/dijkstra.clj

Last active March 21, 2022 15:01
Download ZIP

Revisions

  1. loganlinn revised this gist Apr 22, 2013. 1 changed file with 2 additions and 0 deletions.
    2 changes: 2 additions & 0 deletions dijkstra.clj
    View file
    Original file line number Diff line number Diff line change
    @@ -1,3 +1,5 @@
    (def ^:private inf (Long/MAX_VALUE))

    (defn neighbors
    "Returns n's neighbors, optionally filtered if unvisited"
    ([g n] (get g n {}))
  2. loganlinn revised this gist Apr 22, 2013. 1 changed file with 7 additions and 5 deletions.
    12 changes: 7 additions & 5 deletions dijkstra.clj
    View file
    Original file line number Diff line number Diff line change
    @@ -4,12 +4,14 @@
    ([g n uv] (select-keys (neighbors g n) uv)))

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

    (defn dijkstra
    "Returns a mapping of nodes to minimum cost from src using Dijkstra algorithm.
  3. loganlinn created this gist Apr 22, 2013.
    30 changes: 30 additions & 0 deletions dijkstra.clj
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,30 @@
    (defn neighbors
    "Returns n's neighbors, optionally filtered if unvisited"
    ([g n] (get g n {}))
    ([g n uv] (select-keys (neighbors g n) uv)))

    (defn update-costs
    "Returns "
    [g costs curr unvisited]
    (reduce
    (fn [c [nbr nbr-cost]] (update-in c [nbr] (partial min (+ (c curr) nbr-cost))))
    costs
    (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.
    Optionally, specify :target node to return only the min price for target"
    [g src & {:keys [target]}]
    (loop [costs (assoc (zipmap (keys g) (repeat inf)) src 0)
    curr src
    unvisited (disj (apply hash-set (keys g)) src)]
    (if (or (empty? unvisited) (= inf (costs curr)))
    costs
    (let [costs' (update-costs g costs curr unvisited)
    curr' (first (sort-by costs' unvisited))]
    (if (= target curr)
    (costs' target)
    (recur costs'
    curr'
    (disj unvisited curr')))))))