1対全最短路問題を計算した実行時間と計算量をうまい具合にフィッティングしてみた。GNUPLOT にもそういった機能があるのだが、今回は自分でパラメータ調整をするという何とも原始的な方法で行ったため、あまり突っ込みを入れてもらいたくはないところ。
まずは1対全最短路問題を解いたときの結果であるが、Binary-Heap と Multi-Level Buckets がほぼ同じような特性を示している。やはり計算量での差は大きく見れば定数分の差なので、このように実装上の改善が十分効いている事がよくわかる。