グラフ（応用）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（ワーシャルフロイド）

事前に必要な知識

動的計画法の基礎

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

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

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

テック企業求人一覽

こちらの求人をrecoから紹介されたものです。 recoは現役の外資エンジニアがモックインタビュー付きで面接対策を行ってくれる転職サービスです。これらの企業にどのように準備に準備して振る舞えば採用されるのか的確なアドバイスを受ける事ができます。 InterviewCatの共著者のgaijineersさんが創業者として皆さんの転職をサポートします。