文系 Hadooper でも分かる Dijkstra アルゴリズム - cocoatomo衝動日記〈移行後版〉今日の Hadoop ソースコードリーディングで Dijkstra アルゴリズムの知名度が低かったので, 解説を書いてみたぜ. このアルゴリズムを一言で説明すると? グラフ上のある始点からあるノードへの最短経路とその距離を求めるアルゴリズム. 用語が分かんないんだけど... グラフというと y = 2x とかを思い浮かべるかもしれないが, この場合の「グラフ」というのは「いくつかの丸 (= ノード, 節) を線 (= エッジ, 辺) でつないだもの」で, 状態遷移図もグラフの一種. 状態遷移図は「有向グラフ」と呼ばる. 丸と丸とをただの線ではなく矢印でつなぐので「有向」=「向きが付いている」と言う. "DAG" は "Directed Acyclic Graph" の略で「非循環有向グラフ」と訳される. "Directed" と "Acyclic" の順序が逆になってるのは気にせんでくれい
