ヒープ付きダイクストラ法

ヒープ付きのダイクストラ法のプログラムを実行してみたが、計算量は O(((n+m)log n)なので、確かに枝の数(m)が点の数(n)のたかだか数倍ぐらいならば、確かに速い。100万点, 400万枝でも p2p (1対1)探索でも 1秒ぐらいしかかからない。もう少し高速化できそうな気もするが、さすがに何千万点ともなると瞬時に解くというわけにはいかない。やはり前処理によるグラフネットワークの簡略化が必要になる。