エントリーの編集
![loading...](https://b.st-hatena.com/bdefb8944296a0957e54cebcfefc25c4dcff9f5f/images/v4/public/common/loading@2x.gif)
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
C++で全N点間の距離を最速計算するアルゴリズムはどう書けばいいでしょう? | mond
記事へのコメント0件
- 注目コメント
- 新着コメント
このエントリーにコメントしてみましょう。
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
![アプリのスクリーンショット](https://b.st-hatena.com/bdefb8944296a0957e54cebcfefc25c4dcff9f5f/images/v4/public/entry/app-screenshot.png)
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
C++で全N点間の距離を最速計算するアルゴリズムはどう書けばいいでしょう? | mond
N頂点あるグラフの全部の2頂点間の距離を求める場合、負の距離を含むグラフならベルマンフォード法、そ... N頂点あるグラフの全部の2頂点間の距離を求める場合、負の距離を含むグラフならベルマンフォード法、そうでないならワーシャルフロイド法を使うというのが教科書的な回答ですが、それの最速を目指す場合どうすればいいか、という話でしょうか。 ワーシャルフロイド法自体は3重ループを用いる比較的重いアルゴリズムで、計算の途中経過の状態を次の最短経路の計算に用いる動的計画法なので並列化や高速化は自明ではないのですが、探した所トロピカル演算を用いて行列積に似た計算に落とし込むという手があるそうです。 動的計画法を実現する代数〜トロピカル演算でグラフの最短経路を計算する〜 - Qiitaトロピカル半環と呼ばれる代数構造上のトロピカル行列を利用すると動的計画法を使ってグラフの最短経路の距離を計算するという問題が単純な行列積で解けてしまうらしい。そんな噂12を聞きつけて我々はその謎を解き明かすべく南国(トロピカル)