さて前回の記事ではそこそこうまくいった例を示したが、それにしてももう少し性能が出てもいいのでは?という疑問が残る。思い当たる原因はいくつかあるのだが、まずはグラフの規模を疑い、今回は全米グラフを用いる。各クエリに対応した forward-search(F-time), backward-search(B-time), bidirectional-search(D-time) の実行時間をまとめる。
![](https://blogimg.goo.ne.jp/user_image/3c/9c/fa57d94cd903af3bb76bc11df641b5db.png)
Query[0] (17261435, 8424294) のように近い場合では、どれも同程度の実行時間で終了する。
![](https://blogimg.goo.ne.jp/user_image/5a/4b/533381069765cfd5a96faf3cb2999b48.png)
Query[8] (18549540, 3230879) のようにうまく探索範囲を狭ませることのできる場合では、forward-search に比べて bidirectional-search の方が効率的ではある。冷静に考えると backward-search の方が良いが。
![](https://blogimg.goo.ne.jp/user_image/57/99/2ce689705b9e85ad6a6ab86df8edb6c4.png)
Query[9] (957498, 10453327) のように遠い場合では、探索範囲自体は狭まっているのだが、実行時間はむしろ増えてしまっている。
Graph : USA-road-d.USA.gr (23,947,347 nodes 58,333,344 arcs) Query : P2P x 10 CPU : Intel(R) Xeon(R) CPU X5460 @ 3.16GHz
![](https://blogimg.goo.ne.jp/user_image/3c/9c/fa57d94cd903af3bb76bc11df641b5db.png)
Query[0] (17261435, 8424294) のように近い場合では、どれも同程度の実行時間で終了する。
![](https://blogimg.goo.ne.jp/user_image/5a/4b/533381069765cfd5a96faf3cb2999b48.png)
Query[8] (18549540, 3230879) のようにうまく探索範囲を狭ませることのできる場合では、forward-search に比べて bidirectional-search の方が効率的ではある。冷静に考えると backward-search の方が良いが。
![](https://blogimg.goo.ne.jp/user_image/57/99/2ce689705b9e85ad6a6ab86df8edb6c4.png)
Query[9] (957498, 10453327) のように遠い場合では、探索範囲自体は狭まっているのだが、実行時間はむしろ増えてしまっている。
![](https://blogimg.goo.ne.jp/user_image/63/2c/c6ec295fe3c02607cb75669e2914de9f.png)