詳しくは添付の図を見ていただくとして、全米データでは 点数 n = 2400 万点, 枝数 m = 5800 万枝なので、優先キューなどを用いない原始的なダイクストラ法では計算量が O(n^2) になって、2400 万の二乗で計算量が計上される。一方、例えば 2-heap を用いたダイクストラ法の計算量は O(m log n) であるが、n = 23,947,347 でも log n = 約17 にしかならないので、実際には m (枝数) によって計算量が決定される。道路データでは点は交差点を表す場合が多いが、点の次数(つまり交差点に接続している道路)は多くても4程度なので、グラフはかなり疎になる(つまり n^2 >> m となる)。 ただし、理論計算量(最悪時想定)が小さい方が、ソフトウェアの性能においても上回るとは限らない。それは以下のような原因が考えられる。 1:最悪の場合はめったに