Реализовать алгоритм Дейкстры

@GoldenChild · Регистрация: 12.06.2013

Студворк — интернет-сервис помощи студентам

Нужно реализовать алгоритм Дейкстры на Lisp. В интернете нашел такое вот решение, только MuLisp ругается на функцию neighbours. Подскажите пожалуйста в чем там проблема, а возможно у кого-то есть свое решение.

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
$(defun get-nodes (edges)
    
    (defun add-node (e)
            (if (member e nodes)
                nodes
                (setq nodes (cons e nodes))
        )
    )
 
        (setq nodes nil)
 
        (mapcar '(lambda (edge) (add-node (car edge)) (add-node (cadr edge))) edges)
        
    nodes
)
 
$(defun myeq(a b)
    (if (eql a b))
        (nil)   
)
 
$(defun dijkstra (edges from)
    (setq d (list (cons from 0)))
    (setq p (list (cons from from)))
    (setq v (get-nodes edges))
    (setq u nil)
    
    (mapcar '(lambda (node) (setq d (append d (list (cons node 999))))) v)
    (mapcar '(lambda (node) (setq p (append p (list (cons node nil))))) v)
    
    (defun neighbours (node ledges)
         (mapcar 'cadr (remove-if-not '(lambda (e) (eq node (car e))) ledges))
    )
    
    
    (defun unvisited ()
        (remove-if '(lambda (n) (find (cadr n) u)) edges)
    )
    
 
    (defun get-minimal-unvisited ()
        (car (car (sort (remove-if '(lambda (n) (find (car n) u)) d) '(lambda (a b) (< (cdr a) (cdr b))))))
    )
    
 
    (defun relax (node)
        (if (> (cdr (assoc node d)) (+ 1 (cdr (assoc current d))))
        (progn
            (rplacd (assoc node d) (+ 1 (cdr (assoc current d))))
            (rplacd (assoc node p) (cons (cdr (assoc current p)) node)))
        nil)
    )
 
    (defun dijkstra-helper ()
        (if (< (length u) (length v))
            (progn
                (setq current (get-minimal-unvisited))
                (setq u (cons current u))
                (mapcar 'relax (neighbours current (unvisited)))
                (dijkstra-helper)
            )
            
            nil)
    )
    
    (dijkstra-helper)
    (list d p)
 
)
 
$(print (dijkstra '((1 2) (1 3) (1 6) (2 1) (2 3) (2 4) (3 1) (3 2) (3 4) (3 6) (4 2) (4 3) (4 5) (5 4) (5 6) (6 1) (6 3) (6 5)) 1))

@Catstail · 08.09.2014, 07:36

В какой версии muLisp работаешь? Поддержку CommonLisp подключил?

@GoldenChild · 08.09.2014, 16:11 **[ТС]**

Сообщение от Catstail

В какой версии muLisp работаешь? Поддержку CommonLisp подключил

muLisp-87 generic MS-DOS version 6.10
Насчет поддержки - не знал что ее надо подключить. Как это сделать?

@Catstail · 08.09.2014, 17:45

Запускаешь cmd.exe, заходишь в директорию muLisp и выполняешь:

Bash
1
l.com common.lsp

файл common.lsp (дл 13К) должен быть в текущей директории. Потом загружаешь свои функции.

@GoldenChild · 08.09.2014, 20:19 **[ТС]**

Сообщение от Catstail

Потом загружаешь свои функции.

Все равно все те же ошибки. Может попробуешь запустить этот код у себя, если заработает, то буду искать проблему не в коде.

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
(let ( (nodes) )
  (defun get-nodes (edges)
    (defun add-node (e)
      (if (member e nodes)
        nodes
        (setq nodes (cons e nodes))))
 
    (setq nodes nil)
 
    (mapcar #'(lambda (edge) (add-node (car edge)) (add-node (cadr edge))) edges)
    nodes))
 
;; (print (get-nodes '((1 2) (2 3) (1 5) (2 4) (4 1))))
 
(let ( (d) (p) (v) (u) )
  (defun dijkstra (edges from)
    (setq d (list (cons from 0)))
    (setq p (list (cons from from)))
    (setq v (get-nodes edges))
    (setq u nil)
 
    (mapcar #'(lambda (node) (setq d (append d (list (cons node 99999))))) v)
    (mapcar #'(lambda (node) (setq p (append p (list (cons node nil))))) v)
 
    (defun neighbours (node ledges)
      (mapcar #'cadr (remove-if-not #'(lambda (e) (eq node (car e))) ledges)))
 
    (defun unvisited ()
      (remove-if #'(lambda (n) (find (cadr n) u)) edges))
 
    (defun get-minimal-unvisited ()
      (car (car (sort (remove-if #'(lambda (n) (find (car n) u)) d) #'(lambda (a b) (< (cdr a) (cdr b)))))))
 
    (let ( (current) )
 
      (defun relax (node)
        (if (> (cdr (assoc node d)) (1+ (cdr (assoc current d))))
          (progn
            (rplacd (assoc node d) (1+ (cdr (assoc current d))))
            (rplacd (assoc node p) (cons (cdr (assoc current p)) node)))
          nil))
 
      (defun dijkstra-helper ()
        (if (< (length u) (length v))
          (progn
            (setq current (get-minimal-unvisited))
            (setq u (cons current u))
            (mapcar #'relax (neighbours current (unvisited)))
            (dijkstra-helper))
          nil)))
 
    (dijkstra-helper)
    (list d p)))
 
(print (dijkstra '((1 2) (1 3) (1 6) (2 1) (2 3) (2 4) (3 1) (3 2) (3 4) (3 6) (4 2) (4 3) (4 5) (5 4) (5 6) (6 1) (6 3) (6 5)) 1))

@Catstail · 08.09.2014, 20:39

Посмотрел на функции более внимательно... Странно они выглядят. defun в defun-e - это сильно! Что-то не так.

@VH · 08.09.2014, 21:31

https://www.cyberforum.ru/post6111981.html

Новые блоги и статьи Все статьи Все блоги /
Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек SDL3 и Box2D из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия SDL 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual. . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»

@Catstail Супер-модератор 38177 / 21112 / 4307 Регистрация: 12.02.2012 Сообщений: 34,716 Записей в блоге: 14
	08.09.2014, 07:36
	В какой версии muLisp работаешь? Поддержку CommonLisp подключил? 0

@Catstail Супер-модератор 38177 / 21112 / 4307 Регистрация: 12.02.2012 Сообщений: 34,716 Записей в блоге: 14
	08.09.2014, 20:39
	Посмотрел на функции более внимательно... Странно они выглядят. defun в defun-e - это сильно! Что-то не так. 0

@VH 431 / 259 / 23 Регистрация: 23.11.2010 Сообщений: 278
	08.09.2014, 21:31
	Сообщение было отмечено GoldenChild как решение Решение https://www.cyberforum.ru/post6111981.html 2

Реализовать алгоритм Дейкстры

Решение