Rosetta Code

Dijkstra's algorithm: Difference between revisions

Page Discussion

Dijkstra's algorithm (view source)

Revision as of 07:33, 9 July 2023

321 bytes removed ,  11 months ago
Update emacs lisp code
m (→‎{{header|Tailspin}}: Add necessary type info)
(Update emacs lisp code)
Line 3,306:
 
<syntaxhighlight lang="lisp">
(defvar path-list '((a b 7)
;; Path format: (start-point end-point previous-point distance)
(a c 9)
(setq path-list `(
(a b ,nilf 714)
(ab c ,nil 910)
(a f ,nil(b d 1415)
(b (c ,nild 1011)
(b d ,nil(c f 152)
(c (d ,nile 116)
(ce f ,nil 29)))
(d e ,nil 6)
(e f ,nil 9)
))
(defun calculate-shortest-path ()
(let ((shortest-path '())
(head-point (nth 0 (nth 0 path-list))))
(defun combine-new-path (path1 path2)
(list (nth 0 path1) (nth 1 path2) (nth 0 path2)
(+ (nth 3 path1) (nth 3 path2))) )
(defun find-shortest-path (start end)
(seq-find (lambda (item)
(and (eq (nth 0 item) start) (eq (nth 1 item) end)))
shortest-path)
)
(defun add-shortest-path (item)
(add-to-list 'shortest-path item) )
(defun process-path (path)
(if (eq head-point (nth 0 path))
(add-to-list 'shortest-path path)
(progn
(dolist (spath shortest-path)
(when (eq (nth 1 spath) (nth 0 path))
(let* ((new-path (combine-new-path spath path))
(spath-found (find-shortest-path (nth 0 new-path)
(nth 1 new-path))))
(if spath-found
(when (< (nth 3 new-path) (nth 3 spath-found))
(setcdr (nthcdr 1 spath-found) (list (nth 2 new-path) (nth 3 new-path)))
)
(add-shortest-path new-path)) ) ) ) ) ) )
 
(defun calculate-shortest-path (path-list)
(let (shortest-path)
(dolist (path path-list)
(add-to-list 'shortest-path (list (nth 0 path)
(nth 1 path)
nil
(nth 2 path))
't))
(dolist (path path-list)
(dolist (short-path shortest-path)
(when (equal (nth 0 path) (nth 1 short-path))
(let ((test-path (list (nth 0 short-path)
(nth 1 path)
(nth 0 path)
(+ (nth 2 path) (nth 3 short-path))))
is-path-found)
(dolist (short-path1 shortest-path)
(when (equal (seq-take test-path 2)
(seq-take short-path1 2))
(setq is-path-found 't)
(when (> (nth 3 short-path1) (nth 3 test-path))
(setcdr (cdr short-path1) (cddr test-path)))))
(when (not is-path-found)
(add-to-list 'shortest-path test-path 't))))))
shortest-path))
 
(defun find-shortest-route (startfrom endto path-list)
(let ((pointshortest-path-list '(calculate-shortest-path path-list))
(end- point-list matched-path enddistance)
(add-to-list 'point-list to)
path-found)
(setq matched-path
(add-to-list 'point-list end)
(seq-find (lambda (path) (equal (list from to) (seq-take path 2)))
(catch 'no-more-path
shortest-path-list))
(while 't
(setq path-founddistance (find-shortest-pathnth start3 endmatched-pointpath))
(if (or (not path-found) (notwhile (nth 2 matched-path-found)))
(add-to-list 'point-list (nth 2 matched-path))
(throw 'no-more-path nil)
(setq to (nth 2 matched-path))
(progn
(setq matched-path
(add-to-list 'point-list (nth 2 path-found))
(seq-find (lambda (path) (equal (list from to) (seq-take path 2)))
(setq end-point (nth 2 path-found)) )
shortest-path-list)))
)
(if matched-path
)
(progn
)
(add-to-list 'point-list startfrom)
(list 'route point-list 'distance distance))
)
nil)))
(defun show-shortest-path (start end)
(let ((path-found (find-shortest-path start end))
(route-found (find-shortest-route start end)))
(if path-found
(progn
(message "shortest distance: %s" (nth 3 path-found))
(message "shortest route: %s" route-found) )
(message "shortest path not found") )
)
(message "--") )
 
(format "%S" (find-shortest-route 'a 'e path-list))
;; Process each path
(dolist (path path-list)
(process-path path) )
(message "from %s to %s:" 'a 'e)
(show-shortest-path 'a 'e)
(message "from %s to %s:" 'a 'f)
(show-shortest-path 'a 'f)
)
)
(calculate-shortest-path)
</syntaxhighlight>
 
Line 3,404 ⟶ 3,373:
 
<pre>
(route (a c d e) distance 26)
from a to e:
shortest distance: 26
shortest route: (a c d e)
--
from a to f:
shortest distance: 11
shortest route: (a c f)
--
</pre>
 
Yong
59

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/346090"