Parallel Shortest Path Algorithm

最短路問題に対する並列アルゴリズムというのを考えたことがあったが、ダイクストラ法というのはポテンシャル最少のノードを見付けて（ここでヒープやバケットが使えるが）、枝の緩和処理を行う。そのため複数ノードに分けて同時に処理するわけにはいかない。枝の緩和処理は枝ごとに並列に処理することが出来るが、実際の道路ネットワークでは、あまりノードの次数が高くないので、これも上手くいかない。各枝の緩和処理を SIMD で行おうと考えたが、やはり次数が高くないので、これも効果は期待薄である。
一方、Bellman-Ford 法やこれに近い方法を並列化した論文なども見かける。通常は枝の費用が全て非負の場合にはダイクストラ法が使えるだが、並列化するのならば Bellman-Ford 法の方がやりやすい。

Parallel Shortest Path Algorithms for Solving Large-Scale Instances

個人的には、並列化しなくてもダイクストラ法をベースにしていろいろと工夫して高速化した方が速いと思っているのだが、この論文で使っている Cray MTA-2 とはどんな計算機だろうか？　噂は聞くのだが、商業的には成功しなかったので、幻の計算機のような感じになっている。