ワーシャルフロイド法をpythonで実装して実行例を丁寧に見る

最短経路問題を解くアルゴリズムの一つで、すべてのグラフの頂点間の最短経路を見つけることができる。本記事では、

pythonのコード
簡単なグラフに適用した際のアルゴリズムの流れ

の2点をまとめます。特に実行例では、初学者(私を含む)の方にもイメージしやすいよう、各辺への操作を一つ一つ丁寧に取り上げています。

ポイント
コード
アルゴリズムの流れの確認
まとめと参考

ポイント

負の重みを持つグラフにも適用可能
負閉路の検出にも適用可能
計算量は $O(V^3)$ ($V$ は頂点の個数)
すべての頂点間の最短経路を計算できる(全点対間最短経路問題)

コード

このアルゴリズムを一言で言うと、『3つの頂点 $i, ,j, k$ を選択し、$k$を経由する経路 $i->k->j$ が経由しない経路 $i->j$ より小さければ、$i->j$ を更新する』という方法です。

def Warshall_Floid(G):
    """
    G: 隣接グラフ
    """

    inf = float('INF') 
    num_nodes = len(G)  #頂点数
    dist = [[inf]*num_nodes for _ in range(num_nodes)] #テーブルを用意

    #テーブルを初期化: 同じ頂点は重み0 かつ　隣接グラフG[From][To]=weight　を入力
    for frm in range(num_nodes):
        dist[frm][frm] = 0 #初期化1 同じ頂点は重み0
        for to, weight in G[frm]:
            dist[frm][to] = weight
    
    #フロイドワーシャル法のコア部分
    for k in range(num_nodes):
        for From in range(num_nodes):
            for To in range(num_nodes):
                if dist[From][k] + dist[k][To] < dist[From][To]:
                    dist[From][To] = dist[From][k] + dist[k][To]
    
    #負閉路の検出 dist[i][i]<0となる頂点iがあれば負閉路が存在
    NEGATIVE_CYCLE = False
    for i in range(num_nodes):
        if dist[i][i] < 0:
            NEGATIVE_CYCLE = True
            break
    
    return dist, NEGATIVE_CYCLE

アルゴリズムの流れの確認

以下のグラフを用いて、視覚的にアルゴリズムの流れを確認します。

このグラフに対する距離のテーブル dist は以下のようになります。ただし、テーブルの行,列の指定は0はじまりとします。

$k=0$ の場合

$i \rightarrow 0 \rightarrow j$ の経路を考えます。ただし、$i,j \in \{1,2,3\}$ です。

例えば $i=3$, $j=1$を注目しますと、$dist_{3,1}=4$ です。これに対して、頂点0を経由するルート$3 \rightarrow 0 \rightarrow 1$ は、$dist_{3,0}+dist_{0,1}=-1+1=0$です。

したがって、$dist_{3,1}=4 > dist_{3,0}+dist_{0,1}=0$ が成り立つため、dist は更新されます。

同様に、$i=3$, $j=2$ も $dist_{3,2}=\infty > dist_{3,0}+dist_{0,2}=1$ が成り立つため、 dist は更新されます。その他の組み合わせは $dist_{i,j} \leq dist_{i,0}+dist_{0,j}$のため更新されません。

結果、以下のようなテーブルになります。赤字は更新された数字です。

$k=1$ の場合

すべて $dist_{i,j} \leq dist_{i,1}+dist_{1,j}$ となり、更新はありません。

$k=2$ の場合

$i=0$, $j=3$ の場合のみ、 $dist_{0,3}=\infty > dist_{0,2}+dist_{2,3}=3$ となって更新されます。

$k=3$ の場合

更新されるのは以下の2つです。

$i=2$, $j=0$ の場合: $dist_{2,0}=\infty > dist_{2,3}+dist_{3,0}=0$
$i=2$, $j=1$ の場合: $dist_{2,1}=\infty > dist_{2,3}+dist_{3,1}=1$

まとめと参考

ワーシャルフロイド法のpythonでの実装と、アルゴリズムの流れをメモしました。

上記のpythonコードは AOJ GRL_1_C で正解になることを確認しています。

Aizu Online Judge

最短経路を求める他のアルゴリズム(ベルマンフォード法、ダイクストラ法)については以下の私の記事でも述べています。ご興味があればぜひ。

ベルマンフォード法

ダイクストラ法

https://output-zakki.com/dijkstra_python/

記事の執筆には、以下の書籍を参考にしました。

『プログラミングコンテストチャレンジブック [第2版] 問題解決のアルゴリズム活用力とコーディングテクニックを鍛える』, 秋葉拓哉、岩田陽一、北川宜稔, マイナビbooks, 2012年

『問題解決力を鍛える！アルゴリズムとデータ構造』, 大槻兼資・著　秋葉拓哉・監修, 講談社サイエンティフィク, 2020年

[ワーシャルフロイド法]pythonでの実装と実行例を丁寧に