C++で全N点間の距離を最速計算するアルゴリズムはどう書けばいいでしょう？ | mond

N頂点あるグラフの全部の2頂点間の距離を求める場合、負の距離を含むグラフならベルマンフォード法、そうでないならワーシャルフロイド法を使うというのが教科書的な回答ですが、それの最速を目指す場合どうすればいいか、という話でしょうか。 ワーシャルフロイド法自体は3重ループを用いる比較的重いアルゴリズムで、計算の途中経過の状態を次の最短経路の計算に用いる動的計画法なので並列化や高速化は自明ではないのですが、探した所トロピカル演算を用いて行列積に似た計算に落とし込むという手があるそうです。 動的計画法を実現する代数〜トロピカル演算でグラフの最短経路を計算する〜 - Qiitaトロピカル半環と呼ばれる代数構造上のトロピカル行列を利用すると動的計画法を使ってグラフの最短経路の距離を計算するという問題が単純な行列積で解けてしまうらしい。そんな噂12を聞きつけて我々はその謎を解き明かすべく南国（トロピカル）