17 lines
659 B
Common Lisp
17 lines
659 B
Common Lisp
(defvar *r* nil)
|
|
|
|
(defun dijkstra-short-paths (z w)
|
|
(loop for (a b) in (loop for v on z nconc
|
|
(loop for e in (cdr v)
|
|
collect `(,(car v) ,e)))
|
|
do (setf *r* nil) (paths w a b 0 `(,a))
|
|
(format t "~{Path: ~A Distance: ~A~}~%"
|
|
(car (sort *r* #'< :key #'cadr)))))
|
|
|
|
(defun paths (w c g z v)
|
|
(if (eql c g) (push `(,(reverse v) ,z) *r*)
|
|
(loop for a in (sort (cdr (assoc c w)) #'< :key #'cddr)
|
|
for b = (cadr a) do (unless (member b v)
|
|
(paths w b g (+ (cddr a) z)
|
|
(cons b v))))))
|