括弧の山と戦ってみた：ダイクストラ法って何だよ，分かんねぇよ。

1. この記事で学べること・学べないこと

学べること

• 何もない。

2. 実際のコード

　ダイクストラ法というものを理解しようと書いてみたけれど，分からな過ぎて投げた。
　自分があとから見返して，笑える日が来るように貼るだけ貼っておく。

dijkstra.lisp

(defparameter *nodes* '(tokyo takasaki nagano nagoya niigata hukui kyoto))
(defparameter *edges* '((tokyo takasaki 110) (takasaki tokyo 110) (tokyo nagano 230) (nagano tokyo 230) (tokyo nagoya 350) (nagoya tokyo 350) (takasaki nagano 130) (nagano takasaki 130) (nagano nagoya 280) (nagoya nagano 280) (takasaki niigata 210) (niigata takasaki 210) (nagano hukui 330) (hukui nagano 330) (nagoya kyoto 160) (kyoto nagoya 160) (niigata hukui 250) (hukui niigata 250) (hukui kyoto 190) (kyoto hukui 190)))

(defun edges-from (node edges)
  (labels ((start-with-p (edge)
     (eq (car edge) node)))
   (remove-if-not #'start-with-p edges)))

(defun edge-length (edge)
  (cadr edge))

(defun adjacent-edges (nodes edges)
  (let ((ret '()))
    (mapc (lambda (node)
            (mapc (lambda (edge)
                    (push edge ret))
                  (edges-from node edges)))
          nodes)
    ret))

(defun remove-visited-edges (visited-edges edges)
  (let ((not-visited '()))
    (mapc (lambda (edge)
            (labels ((visited-p (edge visited-edges)
                                (member edge visited-edges :test #'equal)))
              (if (visited-p edge visited-edges)
                t
                (push edge not-visited))))
          edges)
    not-visited))

(defun equivalent-edge (edge)
  `(,(cadr edge) ,(car edge) ,(caddr edge)))

(defun shortest-edge (edges)
  (let ((shortest (car edges)))
    (mapc (lambda (edge)
            (if (< (caddr edge) (caddr shortest))
              (setf shortest edge)
              t))
          edges)
    shortest))

(defun visited-nodes (visited-edges)
  (let ((nodes (mapcar (lambda (edge)
                         (car edge))
                       visited-edges)))
    (remove-duplicates nodes)))

(defun dijkstra (start-node nodes edges)
  (labels ((main (visited-nodes visited-edges)
                 (let* ((not-visited-edges (remove-visited-edges
                                             visited-edges 
                                             (adjacent-edges visited-nodes edges)))
                       (shortest (shortest-edge not-visited-edges)))
                   (push shortest visited-edges)
                   (push (equivalent-edge shortest) visited-edges)
                   (push (cadr shortest) visited-nodes)
                   shortest)
                 (if (equal nodes visited-nodes)
                   visited-edges
                   (main visited-nodes visited-edges))))
           (main start-node nil)))

(princ (dijkstra '(tokyo) *nodes* *edges*))

3. 雑感

　今度はPythonとかでやってみる。