Help us understand the problem. What is going on with this article?

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

More than 3 years have passed since last update.

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とかでやってみる。

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした