2023 07 31

【アルゴリズム】グラフの最短経路問題

グラフの特性	方法	計算量
負の重みの辺も含むグラフ	Bellman-Ford 法	\(O(\lvert V\rvert \lvert E \rvert\))
辺の重みがすべて非負なグラフ	Dijkstra 法	\(O(\lvert V\rvert ^2)またはO(\lvert E \rvert log \lvert V \rvert)\)
重み付き有向グラフ	Floyd-Warshal 法	\(O(\lvert V \rvert) ^3\)
DAG	動的計画法	\(O(\lvert V\rvert + \lvert E \rvert)\)
重み無しグラフ	幅優先探索	\(O(\lvert V \rvert + \lvert E \rvert)\)

Bellman-Ford 法

始点 s から到達できる負閉路が存在するならばその旨を報告し、始点から到達しうる負閉路が存在しないならば各頂点 v への最短路を求めるアルゴリズム。
負の重みが存在しない場合は Dijkstra 法のほうが高速。

アルゴリズム

初期状態として始点からの距離を、始点は 0、それ以外は無限大に初期化する。
「全辺について、各頂点の最短距離と思われる値を置き換えていく」(計算量 \(|E|\)) の操作を \(V-1\) 回繰り返す。
負の閉路が無ければ全頂点の最短距離が決定する。負の閉路がある場合は V 回目の操作で値の更新が生じることで負の閉路の検出が可能。

# 負の閉路無し
E = [(1, 2), (1, 3), (2, 3), (2, 4), (3, 4), (3, 5), (3, 6), (4, 6), (5, 6)]
W = {1: {2: 5, 3: 4}, 2: {3: -2, 4: 1}, 3: {4: 2, 5: 1, 6: 4}, 4: {6: 3}, 5: {6: 4}}

V = 6

distances = [10**8] * 6
distances[0] = 0
minus_loop = False
for i in range(1, V + 1):
    for s, e in E:
        d = distances[s - 1] + W[s][e]
        if distances[e - 1] > d:
            distances[e - 1] = d

            # V回目に更新が生じる場合は負の閉路あり
            if i == V:
                minus_loop = True

print("Minus Loop: ", minus_loop)
for i in range(V):
    print(f"{i + 1}: {distances[i]}")

"""
Minus Loop:  False
1: 0
2: 5
3: 3
4: 5
5: 4
6: 7
"""

# 負の閉路あり
E = [(1, 2), (1, 3), (2, 3), (2, 4), (3, 4), (3, 5), (3, 6), (4, 2), (4, 6), (5, 6)]
G = {1: {2, 3}, 2: {3, 4}, 3: {4, 5, 6}, 4: {2, 6}, 5: {6}}
W = {
    1: {2: 5, 3: 4},
    2: {3: -2, 4: 1},
    3: {4: 2, 5: 1, 6: 4},
    4: {2: -1, 6: 3},
    5: {6: 4},
}

V = 6

distances = [10**8] * 6
distances[0] = 0
minus_loop = False
for i in range(1, V + 1):
    for s, e in E:
        d = distances[s - 1] + W[s][e]
        if distances[e - 1] > d:
            distances[e - 1] = d

            # V回目に更新が生じる場合は負の閉路あり
            if i == V:
                minus_loop = True

print("Minus Loop: ", minus_loop)
for i in range(V):
    print(f"{i + 1}: {distances[i]}")

"""
Minus Loop:  True
1: 0
2: -1
3: -2
4: 0
5: -1
6: 2
"""

Dijkstra 法

辺の重みが非負数の場合に単一始点最短経路を求めるための最良優先探索によるアルゴリズム。
辺の重みがすべて同一の非負数の場合は幅優先探索のほうが速い。

アルゴリズム

各頂点 \(v\) に対し距離 \(d(v)\) を、始点では \(0\)、それ以外を \(\infty\) に初期化する。
始点から移動できる頂点の距離を更新する。この時、コストが最も小さい頂点の最短距離が確定する。(それ以外はまだ未確定)
以降、最短距離が確定した頂点から移動できる頂点の距離を更新することを繰り返す。(確定済頂点を除く)

実装例

単純な実装例 (計算量 \(O(\lvert V \rvert ^2)\))

from collections import defaultdict
from math import inf

V = [1, 2, 3, 4, 5, 6]
E = [(1, 2), (1, 6), (1, 3), (2, 3), (2, 4), (3, 6), (3, 4), (6, 5), (4, 5)]
W = {
    1: {2: 7, 3: 9, 6: 14},
    2: {1: 7, 3: 10, 4: 15},
    3: {1: 9, 2: 10, 4: 11, 6: 2},
    4: {2: 15, 3: 11, 5: 6},
    5: {4: 6, 6: 9},
    6: {1: 14, 3: 2, 5: 9},
}

G = defaultdict(set)
for a, b in E:
    G[a].add(b)
    G[b].add(a)


# 始点は1
dist = [inf for _ in range(len(V) + 1)]
dist[1] = 0

decision_flags = [False for _ in range(len(V) + 1)]

# 単純なダイクストラ法
# 計算量は|V|^2
for _ in range(len(V)):
    min_dist = inf
    min_v = -1
    # 確定済でない頂点のうち、dist値が最小の頂点を探す
    for v in V:
        if not decision_flags[v] and dist[v] < min_dist:
            min_dist = dist[v]
            min_v = v

    # 見つからなければ終了する
    if min_v == -1:
        break

    # min_vを始点とした各辺を緩和する
    for vv in G[min_v]:
        d = dist[min_v] + W[min_v][vv]
        dist[vv] = min(dist[vv], d)

    # min_vを確定済にする
    decision_flags[min_v] = True

for i in V:
    print(f"vertex-{i}: {dist[i]}")
"""
vertex-1: 0
vertex-2: 7
vertex-3: 9
vertex-4: 20
vertex-5: 20
vertex-6: 11
"""

ヒープを用いた高速化 (計算量 \(O(\lvert E \rvert log\lvert V \rvert )\))
ただし疎グラフ (\(\lvert E \rvert = O(\lvert V \rvert)\)) である場合。密グラフ (\(|E|=O(|V|^2)\)) の場合は単純なダイクストラ法のほうが高速になる。

from collections import defaultdict
from math import inf
import heapq

V = [1, 2, 3, 4, 5, 6]
E = [(1, 2), (1, 6), (1, 3), (2, 3), (2, 4), (3, 6), (3, 4), (6, 5), (4, 5)]
W = {
    1: {2: 7, 3: 9, 6: 14},
    2: {1: 7, 3: 10, 4: 15},
    3: {1: 9, 2: 10, 4: 11, 6: 2},
    4: {2: 15, 3: 11, 5: 6},
    5: {4: 6, 6: 9},
    6: {1: 14, 3: 2, 5: 9},
}

G = defaultdict(set)
for a, b in E:
    G[a].add(b)
    G[b].add(a)


# 始点は1
dist = [inf for _ in range(len(V) + 1)]
dist[1] = 0

decision_flags = [False for _ in range(len(V) + 1)]

q = [(0, 1)]

while q:
    d, v = heapq.heappop(q)
    if decision_flags[v]:
        continue

    decision_flags[v] = True

    for vv in G[v]:
        if decision_flags[vv]:
            continue

        new_d = d + W[v][vv]
        if new_d < dist[vv]:
            dist[vv] = new_d
            heapq.heappush(q, (new_d, vv))

for i in V:
    print(f"vertex-{i}: {dist[i]}")
"""
vertex-1: 0
vertex-2: 7
vertex-3: 9
vertex-4: 20
vertex-5: 20
vertex-6: 11
"""

Floyd-Warshall 法

重み付き有向/無向グラフの全ペアの最短経路問題を多項式時間で解くアルゴリズム。
同一頂点間の最短距離が負となる頂点が存在する場合は、負閉路が存在することになる。

アルゴリズム

頂点 \(0 \sim k\) を通ってもよい場合の \(i\) から \(j\) への最短距離を \(d_{k,i,j}\) とする。
最短距離は以下の 2 パターンのどちらかになる。 1. 頂点 \(k\) を通らずに \(i\) から \(j\) へ到達する 2. 頂点 \(k\) を通り \(i\) から \(j\) へ到達する
1 の時、最短距離は頂点 \(0 \sim k-1\) を通ってもよい場合の最短距離と一致する。

\(d_{k,i,j} = d_{k-1,i,j}\)

2 の時は頂点 \(0 \sim k-1\) を通ってもよい場合の \(i\) から \(k\) への最短距離と、\(k\) から \(j\) への最短距離の和になる。

d_{k,i,j} = d_{k-1,i,k} + d_{k-1, k, j}

したがって最短距離 \(d_{i,j,k}\) は以下のようになる。

\(d_{k,i,j} = min(d_{k-1,i,j}, \quad d_{k-1,i,k} + d_{k-1, k,j})\)

これを利用して DP(動的計画法) で最短距離を求める。
ただし、実際の実装では 3 次元にする必要はなく、\(k\) から \(k+1\) の更新を in-place に実現できる。

実装例

from math import inf


V = [1, 2, 3, 4, 5, 6]
E = [(1, 2), (1, 3), (2, 3), (2, 4), (3, 4), (3, 5), (3, 6), (4, 2), (4, 6), (5, 6)]
W = {
    1: {2: 5, 3: 4},
    2: {3: -2, 4: 1},
    3: {4: 2, 5: 1, 6: 4},
    4: {2: -1, 6: 3},
    5: {6: 4},
}

dp = [[inf for _ in range(len(V))] for _ in range(len(V))]
# 初期化
for a, b in E:
    dp[a - 1][b - 1] = W[a][b]
for i in range(len(V)):
    dp[i][i] = 0

for k in range(len(V)):
    for i in range(len(V)):
        for j in range(len(V)):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

for d in dp:
    print(d)
"""
[0, 4, 2, 4, 2, 5]
[inf, -1, -3, -1, -3, 0]
[inf, 1, -1, 1, -1, 2]
[inf, -2, -4, -2, -4, -1]
[inf, inf, inf, inf, 0, 4]
[inf, inf, inf, inf, inf, 0]
"""

E - Souvenir