This is a multi-part message in MIME format.
--------------32DD3227C3172DD5129C4A2F
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
I have written the Dijkstra algorithm (described at
http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/dijkstra.html).
1) Could anybody give me a suggestion how to improve my coding style and
make the attached implementation more Lisp and efficient? E.g. the use
of +infinity+ should be eliminated, or extract-cheapest should be
implemented more efficiently.
2) Is there a Lisp code for graph algorithms as Euler cycle, Chinese
Postman Problem, Rural Chinese Postman Problem, etc.?
Thanks
Tomas
--------------32DD3227C3172DD5129C4A2F
Content-Type: text/plain; charset=us-ascii;
name="dijkstra.lisp"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
filename="dijkstra.lisp"
;;; Dijkstra algorithm. For more details see
;;; http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/dijkstra.html
(defmacro adjacent (u graph)
`(cdr (nth ,u ,graph)))
(defvar +infinity+ 100000)
(defun dijkstra (graph start)
(let* ((n (length graph))
(d (make-array n :initial-element +infinity+))
(p (make-array n :initial-element nil))
(s nil)
(v (mapcar #'car graph)))
(setf (svref d start) 0)
(flet ((extract-cheapest ()
(do ((new nil)
(cheapest nil)
(current (pop v) (pop v)))
((null current)
(progn
(setq v new)
cheapest))
(if (null cheapest)
(setq cheapest current)
(if (<= (svref d cheapest) (svref d current))
(push current new)
(progn
(push cheapest new)
(setq cheapest current))))))
(relax (i j w)
(when (> (svref d j)
(+ w (svref d i)))
(setf (svref d j) (+ w (svref d i)))
(setf (svref p j) i))))
(do ((i (extract-cheapest) (extract-cheapest)))
((null v) (list d p s))
(push i s)
(dolist (a (adjacent i graph))
(relax i
(car a)
(if (cadr a) (cadr a) 1)))))))
#|
(defvar graph1 '((0 (1) (2))
(1 (2) (3))
(2 (3) (4))
(3 (4) (0))
(4 (1))))
(adjacent 0 graph1)
(adjacent 1 graph1)
(adjacent 2 graph1)
(adjacent 3 graph1)
(adjacent 4 graph1)
(dijkstra graph1 0)
(dijkstra graph1 1)
(dijkstra graph1 2)
(dijkstra graph1 3)
(dijkstra graph1 4)
; The following example is taken from
; http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/dijkstra.html
(defvar graph2 '((0 (1 4) (3 85))
(1 (0 74) (2 18) (4 12))
(2 (1 12) (5 74) (9 12))
(3 (4 32) (6 38))
(4 (3 66) (5 76) (7 33))
(5 (9 21) (8 11))
(6 (7 10) (3 12))
(7 (6 2) (8 72))
(8 (7 18) (5 31) (9 78))
(9 (5 8))))
(dijkstra graph2 0)
|#
--------------32DD3227C3172DD5129C4A2F--