熊崎 宏樹:N頂点あるグラフの全部の2頂点間の距離を求める場合、負の距離を含むグラフならベルマンフォード法、そうでないならワーシャルフロイド法を使うというのが教科書的な回答ですが、それの最速を目指す場合どうすればいいか、という話でしょうか。 ワーシャルフロイド法自体は3重ループを用いる比較的重いアルゴリズムで、計算の途中経過の状態を次の最短経路の計算に用いる動的計画法なので並列化や高速化は自明ではないのですが、探した所トロピカル演算を用いて行列積に似た計算に落とし込むという手があるそうです。 動的計画法を実現する代数〜トロピカル演算でグラフの最短経路を計算する〜 - Qiita トロピカル半環と呼ばれる代数構造上のトロピカル行列を利用すると動的計画法を使ってグラフの最短経路の距離を計算するという問題が単純な行列積で解けてしまうらしい。そんな噂12を聞きつけて我々はその謎を解き明かすべく南国（トロピカル）の奥地... https://qiita.com トロピカル演算とは「足し算の代わりに2項の最小値を求める」「掛け算の代わりに2項の和を求める」という方法で、行列積の内部で行われる「積と和」を「和と最小」に置き換える事でちょうどワーシャルフロイド法がやっている「点Aから点Bまでの間のコストをあらゆる頂点を経由した場合での最小コスト値で埋める」という操作になるようです。行列積も3重ループの充分重い計算ですがキャッシュのブロッキング等の高速化テクニックが研究されていますので計算オーダーを落とさない範囲内で高速化が見込めるかも知れません。 別の方法として、NVIDIAのGPU(Hopperアーキテクチャ)では動的計画法を援護する専用の命令セットが追加されておりワーシャルフロイド法がデモとして発表されています。 NVIDIA Hopper GPU Architecture Accelerates Dynamic Programming Up to 40x Using New DPX Instructions | NVIDIA Blog The NVIDIA Hopper GPU architecture will accelerate dynamic programming by up to 40x with new DPX instructions.  https://blogs.nvidia.com > In a server with four NVIDIA H100 GPUs, Floyd-Warshall acceleration is boosted > 40x compared to a traditional dual-socket CPU-only server. > > 4枚のH100GPUを搭載したサーバーでは、従来のデュアルソケットCPUのみのサーバーと比較して、ワーシャルフロイド法が40倍速になります。 命令セットの詳細は知らないですがCPUで頑張るよりGPUをフル活用するほうがメモリ帯域なども桁違いに速いため「最速計算」に近いかも知れません。 以上参考になりましたら幸いです。