全点対間最短経路¶

Warshall-Floyd法¶

概要¶

動的計画法により、グラフに含まれる全ての点対に対する最小移動コストを求めるアルゴリズム。

有向グラフ・無向グラフのいずれにも適用可能。また、辺の重みは負であってもよい。

アルゴリズム¶

グラフ \(G(V, E)\) 上のある2点 \((i, j)\) 間の移動に関して、中継ノード \(k\) を考える。
「ノード \(k\) を経由して、 \((i, k)\) と \((k, j)\) をこの順に移動するコスト」と「ノード \((i, j)\) を移動するコスト」を比較し、コストの小さいほうを最小コストとして採用する。
全てのノードを中継ノードとして順次採用し、コストを更新していく。
全中継ノードを調べ終わった時点で、全ての点対の最小コストが求まっている。

計算量はノード数 \(V\) に対し \(\mathcal{O}(V^3)\) となる。

実装¶

[1]:

def warshall_floyd(N, G):
    """任意の2点間の最小移動コストを求める
    N: ノード数
    G: 隣接行列
    return: 最小コストで更新された隣接行列
    """
    for k in range(N):
        for i in range(N):
            for j in range(N):
                if G[i][j] > G[i][k] + G[k][j]:
                    G[i][j] = G[i][k] + G[k][j]
    return G

[2]:

INF=10**7
N = 5
G = [
    [0, 4, 3, INF, INF],
    [4, 0, 2, 5, INF],
    [3, 2, 0, 7, 9],
    [INF, 5, 7, 0, 11],
    [INF, INF, 9, 11, 0]
    ]
H = warshall_floyd(N, G)
print(H[0][4])