I've just implemented Dijkstra's algorithm, and as far as I can tell, it
works.
However, I'm a little concerned at the efficiency. Specifically, I am
using sorted sets, and I can't break apart the set into first/next and keep
it as a set. I have to get next as a sequence and then apply sorted-set-by
to that sequence. This seems like a lot of wasted time. Is there a better
way, or is it not a problem?
Thanks.
;;; The dijkstra's algorithm values look like this!
;;; [end-node [path path-weight]]
;;; [:A [[] 0]]
;;; [:B [[:A :B] 3]]
;;; [:C [[:A :B :C] 5]]
(defn d-comp
"The comparator for Dijkstra's algorithm!"
[[_ [_ a]] [_ [_ b]]]
(<= a b))
(defn dijkstra
"Computes a shortest-path tree starting at the specified node."
[graph start-node]
(loop [acc {}
q (sorted-set-by d-comp [start-node [[start-node] 0]])]
;; Loop until the queue is empty, then return the accumulator
(if (empty? q)
acc
(let [;; Destructure the first element of the queue
[cur-node [cur-path cur-sum]] (first q)
;; Add the first element to the accumulator map
new-acc (conj acc (first q))
;; Pop the first element of the queue
new-q (apply sorted-set-by d-comp (next q)) ;See? Can't just
dequeue the first of the set!
;; Get outgoint links from the current node
;; Only those that either aren't in the accumulator,
;; or which have a shorter path than the accumulator's
;; entry.
links (for [[n w] (graph cur-node)
:when (or (not (acc n))
(< (+ cur-sum w)
(second (acc n))))]
[n [(conj cur-path n)
(+ cur-sum w)]])
;; Get the set of nodes from the links
l-nodes (set (map first links))
;; Filter out the obsolete queue entries. Now,
;; we have better paths.
new-q (apply sorted-set-by d-comp
(filter #(not (l-nodes (first %))) new-q))
;; Combine the queue and the links
new-q (reduce conj new-q links)]
;; Recur on the new values!
(recur new-acc
new-q)))))
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
