Dijkstra's algorithm: Difference between revisions

Content added Content deleted

Inline

@@ Line 1,379: / Line 1,379: @@
 (defun dijkstra-short-paths (z w)
-  (loop for (a b) in (pairs z) do
+  (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~}~%"
-                (short-path w a b))))
+                (car (sort *r* #'< :key #'cadr)))))
-(defun pairs (w)
-  (loop for a in w and d on (cdr w)
-        nconc (loop for e in d collect `(,a ,e))))
-(defun short-path (w i g)
-  (setf *r* nil) (paths w i g 0 `(,i))
-  (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 (nodes c w) for b = (cadr a) do
+      (loop for a in (sort (cdr (assoc c w)) #'< :key #'cddr)
-            (unless (member b v)
+            for b = (cadr a) do (unless (member b v)
-              (paths w b g (+ (cddr a) z) (cons b v))))))
+                                  (paths w b g (+ (cddr a) z)
+                                         (cons b v))))))
-(defun nodes (c w)
-  (sort (cdr (assoc c w)) #'< :key #'cddr))
 </lang>
 {{out}}