最短経路問題で使われるアルゴリズムの1つ。負の閉路がない限り、負の辺があっても使える。グラフ上の全ての頂点間の最短経路を探すので、計算量は$O(V^3)$となる。 ワーシャルフロイド法はその名前から難しそうな印象があって避けていた。しかし、最近競プロの精進中に実装する機会がチラホラあり、実装してみると思ったよりも簡単だったのでびっくりした。ワーシャルフロイド法が必要となった方は簡単な実装なので恐れず調べてみてほしい。 今回すること ワーシャルフロイド法は実装が簡単だが、その裏でどんな振る舞いをしているのかイマイチ掴めなかった。簡単に最短経路を求められるといっても、裏の仕組みを知らずに使うのは自分としてはどうも気持ちが悪い。今回はいろいろ手を動かしてみながら、仕組みの理解を試みる。 C++によるコード まずはワーシャルフロイド法のコードを見てみる。 void warshall_floyd(i
![素人によるワーシャルフロイド法 - Qiita](https://cdn-ak-scissors.b.st-hatena.com/image/square/c5a00ac767ad7283227a019749936828e73db779/height=288;version=1;width=512/https%3A%2F%2Fqiita-user-contents.imgix.net%2Fhttps%253A%252F%252Fcdn.qiita.com%252Fassets%252Fpublic%252Farticle-ogp-background-412672c5f0600ab9a64263b751f1bc81.png%3Fixlib%3Drb-4.0.0%26w%3D1200%26mark64%3DaHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZ3PTk3MiZoPTM3OCZ0eHQ9JUU3JUI0JUEwJUU0JUJBJUJBJUUzJTgxJUFCJUUzJTgyJTg4JUUzJTgyJThCJUUzJTgzJUFGJUUzJTgzJUJDJUUzJTgyJUI3JUUzJTgzJUEzJUUzJTgzJUFCJUUzJTgzJTk1JUUzJTgzJUFEJUUzJTgyJUE0JUUzJTgzJTg5JUU2JUIzJTk1JnR4dC1jb2xvcj0lMjMyMTIxMjEmdHh0LWZvbnQ9SGlyYWdpbm8lMjBTYW5zJTIwVzYmdHh0LXNpemU9NTYmdHh0LWFsaWduPWxlZnQlMkN0b3Amcz02MTFjNjc2YmQwM2ZjMDFkYTk4Yjg1OTI2NGE5NTYwMg%26mark-x%3D142%26mark-y%3D57%26blend64%3DaHR0cHM6Ly9xaWl0YS11c2VyLWNvbnRlbnRzLmltZ2l4Lm5ldC9-dGV4dD9peGxpYj1yYi00LjAuMCZoPTc2Jnc9NzcwJnR4dD0lNDBva2FyeW8mdHh0LWNvbG9yPSUyMzIxMjEyMSZ0eHQtZm9udD1IaXJhZ2lubyUyMFNhbnMlMjBXNiZ0eHQtc2l6ZT0zNiZ0eHQtYWxpZ249bGVmdCUyQ3RvcCZzPTQ5ZmRlOGEyNTU4NzUyM2MwMjQyYTIxZDBhYjgxMWM2%26blend-x%3D142%26blend-y%3D486%26blend-mode%3Dnormal%26s%3De03e3cb98c84aadac756cd8dfa337bfc)