Coding Interview Prep · レッスン

Floyd-Warshall：全点対最短経路

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

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

Q: Coding Interview Prepを始めるのに経験は必要ですか？

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

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

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

Q: このCoding Interview Prepレッスンでコードを書いて実行できますか？

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

3重ループのFloyd-Warshallアルゴリズムで全点対距離行列を埋め、すべての頂点対間の最小ホップ数を求めます。

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

全点対最短経路

Floyd-Warshall は、重み付きグラフにおけるすべてのノードの組の間の最短経路を計算します。負の辺の重みを持つグラフも扱えますが、負の閉路は扱えません。各始点から Dijkstra を実行すると O(V × (V+E) log V) かかりますが、Floyd-Warshall は辺の密度に関係なく O(V³) で実行できます。V ≤ 500 の密グラフでは、Floyd-Warshall のほうが単純で、速度も同程度であることがよくあります。

中心となる考え方：中間ノード

Floyd-Warshall の着眼点は、dp[i][j][k] が、{0, 1, ..., k} のノードだけを中間ノードとして使う、i から j への最短経路を表すことです。最短経路が中間ノードとして k を使う場合と、使わない場合があります。使う場合は dp[i][j][k] = dp[i][k][k-1] + dp[k][j][k-1] です。使わない場合は dp[i][j][k] = dp[i][j][k-1] です。3番目の次元は前方向にしか進まないため、省略でき、配列をその場で更新できます。

距離行列の初期化

まず V×V の行列を用意します。dist[i][i] = 0（自分自身への距離は0）、直接つながる辺については dist[i][j] = weight、辺がない場合は dist[i][j] = inf とします。その後、すべての中間ノード k を順番に処理し、ノードの組 (i, j) を更新します。許可する中間ノードの集合を正しく段階的に増やすため、k の外側のループを最初に置く必要があります。

def floyd_warshall(V, edges):
    INF = float('inf')
    dist = [[INF]*V for _ in range(V)]
    for i in range(V):
        dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = w  # directed graph
    
    for k in range(V):       # intermediate node
        for i in range(V):
            for j in range(V):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    return dist

例を使った完全な実装

4ノードのグラフで Floyd-Warshall の動作を追ってみます。各中間ノード k の処理後、k を経由するより短い経路が見つかるにつれて、行列が埋まっていきます。このアルゴリズムは、最短経路を段階的に構築することで、複数のホップを自然に扱います。

def floyd_warshall(V, edges):
    INF = float('inf')
    dist = [[INF]*V for _ in range(V)]
    for i in range(V):
        dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = w
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dist[i][k] != INF and dist[k][j] != INF:
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist

V = 4
edges = [(0,1,3),(0,2,7),(1,2,1),(1,3,5),(2,3,2)]
dist = floyd_warshall(V, edges)
for row in dist:
    print([x if x != float('inf') else 'INF' for x in row])

負の閉路の検出

Floyd-Warshall の実行後、主対角線を確認します。dist[i][i] < 0 となる要素があれば、ノード i を通る負の閉路が存在します。これは、負の閉路によって i から i へ負のコストで到達できるためです。負の閉路がなければ、対角線上のすべての要素は 0 のままです。

def has_negative_cycle_fw(V, edges):
    dist = floyd_warshall(V, edges)
    for i in range(V):
        if dist[i][i] < 0:
            return True  # negative cycle through node i
    return False

# Negative cycle: 0->1->2->0 with weights 1,-3,1 (sum=-1)
edges_neg = [(0,1,1),(1,2,-3),(2,0,1)]
print(has_negative_cycle_fw(3, edges_neg))  # True

経路の復元

i から j への実際の経路を復元するには、next[i][j] 行列を保持します。最初は、直接つながる辺について next[i][j] = j とします。中間ノード k を経由して更新するときは、next[i][j] = next[i][k] と設定します。経路を復元するには、i から始め、j に到達するまで next のポインタをたどります。これにより、O(V²) の追加領域と、経路1本あたり O(V) の復元時間が必要になります。

def fw_with_path(V, edges):
    INF = float('inf')
    dist = [[INF]*V for _ in range(V)]
    nxt = [[None]*V for _ in range(V)]
    for i in range(V): dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = w; nxt[u][v] = v
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
                    nxt[i][j] = nxt[i][k]
    return dist, nxt

def get_path(nxt, i, j):
    if nxt[i][j] is None: return []
    path = [i]
    while i != j:
        i = nxt[i][j]; path.append(i)
    return path

推移閉包

より単純な変形として、推移閉包は、すべてのノードの組について「ノード i からノード j に到達できるか」を判定します。距離をブール値に置き換え、reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j]) とします。これは、加算と min の代わりにブール値の OR を使う Floyd-Warshall です。reach[i][i] = True と初期化し、直接つながる辺については reach[i][j] = True とします。

def transitive_closure(V, edges):
    reach = [[False]*V for _ in range(V)]
    for i in range(V):
        reach[i][i] = True
    for u, v, _ in edges:
        reach[u][v] = True
    for k in range(V):
        for i in range(V):
            for j in range(V):
                reach[i][j] = reach[i][j] or (reach[i][k] and reach[k][j])
    return reach

edges = [(0,1,1),(1,2,1)]
R = transitive_closure(3, edges)
print(R[0][2])  # True (0 can reach 2 via 0->1->2)

計算量と使いどころ

Floyd-Warshall の計算量は、時間 O(V³)、空間 O(V²) です。V ≤ 300 の密グラフ（E ≈ V²）では、Dijkstra を V 回実行する場合（この場合も O(V³)）より高速です。V = 1000、E = 3000 の疎グラフでは、Dijkstra を V 回実行すると O(V×E×log V) ≈ 33M ですが、Floyd-Warshall は O(V³) = 10⁹ かかるため、Dijkstra のほうが優れています。それぞれを適切に使い分けられるようにしましょう。

すべての頂点対間の最小ホップ数

すべての辺の重みを1に設定します（または、min の代わりに加算を使うFloyd-Warshall法で、真偽値の隣接行列を使用します）：dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])。これにより、すべての頂点対間の最小ホップ数が計算されます。これは、単一の O(V³) のFloyd-Warshallパスで計算する、全点対 BFS の結果です。

def min_hops_all_pairs(V, adj_list):
    INF = float('inf')
    dist = [[INF]*V for _ in range(V)]
    for i in range(V):
        dist[i][i] = 0
        for j in adj_list[i]:
            dist[i][j] = 1
    for k in range(V):
        for i in range(V):
            for j in range(V):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist

adj = [[1,2],[2],[3],[],[]]
print(min_hops_all_pairs(5, adj)[0])  # [0, 1, 1, 2, INF]

面接でFloyd-Warshallについて質問される場面

Floyd-Warshallは、次のような問題についての面接で登場します：(1) 小規模なグラフでの全点対間距離、(2) 総重みが負になる閉路の有無の判定、(3) 制約伝播問題での最短経路の計算、(4) V ≤ 200 の条件で O(V³) の解法を明示的に求める問題。正しさの条件として、3重ループの構造と負閉路が存在しないことを必ず説明してください。

Floyd-Warshallを使った無向グラフ

無向グラフでは、各辺について両方向を追加します：dist[u][v] = dist[v][u] = weight。それ以外のアルゴリズムは同じです。結果の行列は対称になり、すべての頂点対について dist[i][j] == dist[j][i] が成り立ちます。初期化の際に、誤って有向辺として登録しないよう注意してください。無向辺は、3重ループを実行する前の初期行列に両方向で追加する必要があります。

def fw_undirected(V, edges):
    INF = float('inf')
    dist = [[INF]*V for _ in range(V)]
    for i in range(V): dist[i][i] = 0
    for u, v, w in edges:
        dist[u][v] = w
        dist[v][u] = w  # both directions for undirected
    for k in range(V):
        for i in range(V):
            for j in range(V):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist

理解度チェック

このレッスンの Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認しましょう。

レッスンのまとめ

このレッスンでは、Floyd-Warshallは3重のネストしたループと漸化式 dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) によって全点対間の最短経路を計算すること、完了後に dist[i][i] < 0 となる i が存在するかを確認することで負閉路を検出できること、そしてアルゴリズムの時間計算量は O(V³)、空間計算量は O(V²) であることを学びました。次は、Network Delay Time と経路復元のテクニックを使って、最短経路の応用をもう一度扱います。

よくある質問