最短路問題: 双方向探索(bidirectional search) - 4

forward, backward, bidirectional の比較実験。

Graph : USA-road-d.USA.gr (23,947,347 nodes 58,333,344 arcs)
Query : P2P x 10
Queue : 2-ary heap
CPU   : Intel(R) Xeon(R) CPU X5460 @ 3.16GHz

[time] 実行時間
[*-N] 探索した点数 (F:Forward, B:Backward, FB:Bidirectional)
[*-A] 探索した枝数 (F:Forward, B:Backward, FB:Bidirectional)

2-ary heap を使用した事もあるが、いずれも探索した枝数に実行時間が比例している事が分かる。しかしながら、bidirectional-search では、探索コストが少々高いことが伺えるだろう。