詳しくは添付の図を見ていただくとして、全米データでは 点数 n = 2400 万点, 枝数 m = 5800 万枝なので、優先キューなどを用いない原始的なダイクストラ法では計算量が O(n^2) になって、2400 万の二乗で計算量が計上される。一方、例えば 2-heap を用いた…