[ワーシャルフロイド法]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

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

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

図1: 用いるグラフ

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

図2: 距離の2次元テーブル dist

$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}$のため更新されません。

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

図3: $k=0$の場合の更新結果

$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$ となって更新されます。

図4: $k=2$の場合の更新結果

$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$

図5: $k=3$の場合の更新結果

まとめと参考

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

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

Aizu Online Judge

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

ベルマンフォード法

ダイクストラ法

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

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

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

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

コメント