ひとりはみんなのせいで

調べたことの備忘録など

Dijkstra's algorithm

ダイクストラ法についてしっかり勉強したことがなかったので実装してみた。特に新規性はないけど折角書いたので記録しておきます。 グラフはこちらのブログを参考にした。

(def m {:a {:b 5, :c 4, :d 2}
        :b {:a 5, :c 2, :e 6}
        :c {:a 4, :b 2, :c 3, :f 2}
        :d {:a 2, :c 3, :f 6}
        :e {:b 6, :f 4}
        :f {:c 2, :d 6, :e 4}})

(defn dijkstra [from-node to-node m]
  (loop [cur-node from-node ;; 対象ノード
         unfixed-nodes (-> m keys set (disj cur-node)) ;; 未確定ノード
         routes {cur-node {:c 0, :r [cur-node]}}] ;; コストと経路
    (if (empty? unfixed-nodes)
      ;; 未確定ノードがなければ探索終了
      ;; 目標ノードまでのコストと経路を返却
      (routes to-node)
      (let [;; コストと経路を更新
            routes (let [r (routes cur-node)]
                     (->> (m cur-node)
                          (filter #(unfixed-nodes (key %)))
                          ;; 対象ノードと繋がっている各ノードについて
                          ;; 対象ノードから辿った場合のコストと経路を計算
                          (into {} (map (fn [[k v]] [k {:c (+ (:c r) v) 
                                                        :r (conj (:r r) k)}])))
                          ;; これまでより小コストであれば更新
                          (merge-with #(min-key :c % %2) routes))) 
            ;; 確定ノードを検索
            ;; 開始ノードからのコストが最も小さいノードを選定
            [fixed-node _] (->> (for [[k _ :as e] routes :when (unfixed-nodes k)] e) 
                                (apply min-key #(-> % second :c)))]
        (recur fixed-node (disj unfixed-nodes fixed-node) routes)))))

(comment
  (dijkstra :d :e m) ;; => {:c 9, :r [:d :c :f :e]}
  (dijkstra :c :e m) ;; => {:c 6, :r [:c :f :e]}
  )