0Pricing
Competitive Programming Academy · レッスン

Floyd-Warshall 全点対最短経路

あらゆる頂点対の間の最短経路を求めます

「Floyd-Warshall 全点対最短経路」はCoddyKit上の無料Competitive Programming Academyレッスンです。 これはレッスン4/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCompetitive Programming Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Competitive Programming Academyコースには全4レッスンが含まれています。

すべてのペアを一度に求める

1つの始点からだけでなく、ノードのすべてのペア間の最短経路が必要になることがあります。これが全点対最短経路問題です。

Floyd-Warshallを使う

Floyd-Warshallは、3重のわかりやすいループを使い、ほとんど準備なしで全ペアの距離表を作成します。

距離行列

行列を使い、dist[i][j] を i から j までの既知の最小コストとします。最初は、与えられた直接辺から設定します。

dist = [[INF] * n for _ in range(n)]

対角成分を設定する

どのノードもコスト0で自分自身に到達できるため、緩和を始める前に対角成分 dist[i][i] を0に設定します。

for i in range(n):
    dist[i][i] = 0

中間ノードの考え方

ポイントは、経路が中間ノード k を通ることを許し、k 経由の方が直接進むより安いかを調べることです。

ループの順序が重要

外側のループは kにします。これは選択した中間ノードです。内側の i と j のループで、その中間ノードに対してすべてのペアを試します。

for k in range(n):
  for i in range(n):
    for j in range(n):

緩和の手順

各ペアについて k 経由で緩和します。i から k を通って j へ進む方が短ければ、dist[i][j] を合計コストで更新します。

if dist[i][k] + dist[k][j] < dist[i][j]:
    dist[i][j] = dist[i][k] + dist[k][j]

kを外側に置く理由

kの処理が終わるまでに、すべてのペアがk以下の中間ノードを使えるようになります。kを最外ループに置くことで、この保証が正しく保たれます。

負の辺も扱える

Floyd-Warshallは負の辺を扱えますが、負閉路は扱えません。負閉路があると、対角成分の一部が0未満になります。

計算時間

n個のノードに対する3重ループにより、計算量はO(n^3)、空間計算量はO(n^2)です。実用的なのはnが数百程度の場合に限られます。

選ぶべき場面

グラフが小さく密、1つの始点からではなく、すべてのペア間の距離が本当に必要な場合にFloyd-Warshallを選びます。

確認問題

Floyd-Warshallでは、どのループを最外側に置く必要がありますか？

まとめ：Floyd-Warshall

行列を初期化し、対角成分を0にしてから、k、i、jの順にループし、kを経由して緩和します。O(n^3)で全点対最短経路を求められます。🧮

よくある質問

「Floyd-Warshall 全点対最短経路」レッスンは無料ですか？

はい。「Floyd-Warshall 全点対最短経路」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Competitive Programming Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Competitive Programming Academyコースには全4レッスンが含まれています。

「Floyd-Warshall 全点対最短経路」で何を学びますか？

あらゆる頂点対の間の最短経路を求めます ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Competitive Programming Academyを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCompetitive Programming Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン4/4です。

「Floyd-Warshall 全点対最短経路」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCompetitive Programming Academyレッスンでコードを書いて実行できますか？

はい。すべてのCompetitive Programming Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. ヒープを使う Dijkstra 法
  2. Deque による 0-1 BFS
  3. Bellman-Ford と負辺
  4. Floyd-Warshall 全点対最短経路
← Competitive Programming Academyに戻る