グラフ（応用）Warshall-Floyd, 0-1 BFS

LeetCode 練習問題集

問題	難易度	重要度	テクニック
Find the City With the Smallest Number of Neighbors at a Threshold Distance	★★★★	高	Warshall-Floyd
Minimum Obstacle Removal to Reach Corner	★★★★	中	0-1 BFS
Shortest Bridge	★★★★	中	0-1 BFS
Minimum Cost to Make at Least One Valid Path in a Grid	★★★★	中	0-1 BFS

Warshall-Floyd（ワーシャルフロイド）

事前に必要な知識

• 動的計画法の基礎 ワーシャルフロイドは全点対間最短経路問題を効率的に解くアルゴリズムです。全点対間最短経路問題とはその名前の通り全てのノード同士の最短距離を求める問題です。

全点対間最短経路問題はダイクストラを使用しても解くことが可能です。ダイクストラでは決まったあるノード（始点）から他の全てのノードへの最短距離を$\mathrm{O(ElogN)}$または$\mathrm{O(N^2)}$で求めることができます。これを全てのノードに対して実行することで$\mathrm{O(NElogN)}$または$\mathrm{O(N^3)}$で全点対間最短経路問題を解くことができます。

これに対してワーシャルフロイドは$\mathrm{O(N^3)}$で全点対間最短経路問題を解くことができます。以上より、グラフが疎でも密でもダイクストラを使用しても問題はありません。ですが密グラフにおいてはワーシャルフロイドの使用をお勧めします。理由としてはワーシャルフロイドのコード自体はとてもシンプルなものだからです。実際に例題を通して全点対間最短経路問題をワーシャルフロイドで解いてみましょう。