グラフの最短経路探索アルゴリズムの速度計測 - Qiita

探索したグラフの例（各実装において算出された最短経路は、3つとも同一） 計測した環境 iMac (Retina 5K, 27-inch, 2017), 4.2 GHz Intel Core i7, 32 GB 2400 MHz DDR4 macOS Mojave, 10.14.6 python, 3.8.1 実装 （普通の）A*とダイクストラ WikipediaのA*の解説「アルゴリズムの流れ」をほぼそのまま。mの状態判定の順序が違う程度。 _find_candidateが（たぶん）O(n)なので、ノード数が多くなると遅そう。またremoveもたぶんO(n)で遅そう。 なおWikipediaに「優先度付きキュー使え」と書いてあったので heapq を使ってみましたが、生のpython listに対して min(open_list) 等の操作をする実装でも、計算速度が数%遅くなる程度の影響し