Pynote

Python、機械学習、画像処理について

グラフ理論 - ダイクストラ法について

最短経路問題

以下のような重み付きグラフ G を考える。
始点 u 及び終点 v が与えられたとき、uv を結ぶ重みが最小な道を重み最小の u-vといい、その重みを w(u, v) と表す。
2点 u, v が与えられたとき、重み最小の u-v 道を探す問題を最短経路問題 (shortest path problem)という。


ダイクストラ

ダイクストラ法 (Dijkstra's algorithm)は、辺の重みがすべて非負であるグラフの最短経路問題を効率的に解くことができるアルゴリズムである。
負である辺の重みを含むグラフでは、適用できないので注意する。

ダイクストラ法の仕組み

グラフ G、始点 x、終点 y が与えられたとする。
\{u, v\} の重みを w(\{u, v\}) と表すことにする。

重み最小の x-y 道を求めるとき、S \subsetneq V(G)x \in S, y \in V(G) \setminus S となるようにとる。
u から集合 V(G) \setminus S への重み、

\displaystyle
w(x, V(G) \setminus S) = \min_{z \in V(G) \setminus S} w(x, z)

が最小の道、すなわち、点 x から集合 V(G) \setminus S の各点への道のうちで重みが最小のものについて考える。

補題1)
P:x v_1 v_2 \cdots v_k zw(x, V(G) \setminus S) を与える道とすると、v_1 v_2 \cdots v_k \in S

証明)
v_1 v_2 \cdots v_k \notin S と仮定すると、P の中の x から辿って初めて S に含まれない点 v_i が存在する。
すべての辺の重みは非負のため、w(x, v_i) < w(x, z) となり、P の最小性に矛盾する。

補題2)
P 上の x v_1 v_2 \cdots v_k の部分は重み最小の x-v_k 道にある。

証明)
もしそうでないとした場合、x v_1 v_2 \cdots v_k でない重み最小の x-v_k 道が存在することになり、その道に辺 \{v_k, z\} を加えた道のほうが P より重みが最小となるため、P の最小性に矛盾する。

補題1、補題2より、点 x から点 z への重み最小の道は、点 x から点 v_k までの重み最小の道に辺 \{v_k, z\} を加えたものとなるから、その重みは

\displaystyle
w(x, z) = w(x, v_k) + w(\{v_k, z\})

が成り立ち、

\displaystyle
w(x, V(G) \setminus S) = \min_{v_k \in S, \\ z \in V(G) \setminus S} w(x, v_k) + w(\{v_k, z\}) \quad (1)

が得られる。式 (1) を S = \{x\} から Sy が加わるまで繰り返していけば、x から y への重み最小の x-y 道を求めることができる。

アルゴリズム

入力: 重み付きグラフ G、始点 x、終点 y
出力: 重み最小の x-y 道及びその重み
方法:
G の各点 v に対して、各反復ごとにその時点で得られている x から点 v への重み最小のの道の重み d(v) をラベルとして付ける。

1.
点のラベルを初期化する。

\displaystyle
L(v) =
\begin{cases}
    0 & (v = x) \\
    \infty & (otherwise)
\end{cases}

また、始点からの重み最小の道が確定していない点の集合 TT = V(G) として初期化する。

2.
最小のラベル L(v) を持つ点 v \in T を探す。

3.
v = y の場合、終了する。

4.
すべての辺 e = \{v, u\} に対して、u \in T かつ [tex;L(u) > L(v) + w(e)] ならば、
L(u) \leftarrow L(v) + w(e) として更新する。

5.
TT \setminus \{v\} に置き換え、2に戻る。

アルゴリズムの動作例

x = 1, y = 4 とする。

step1:
点のラベル、未確定の点の集合を初期化する。

\displaystyle
\begin{cases}
    L(1) = 0 \\
    L(2) = \infty \\
    L(3) = \infty \\
    L(4) = \infty \\
    L(5) = \infty \\
    L(6) = \infty \\
\end{cases}
T = \{1, 2, 3, 4, 5, 6\}

図は灰色が集合 T の点、水色が集合 V(G) \setminus T の点、青色の文字が各点のラベル L(v) を表す。


step2:
最小のラベルを持つ点を T から探すと、ラベル L(1) = 0 である点 1 が見つかる。

step4:
1 と隣接している集合 T の点は 2, 3, 6 である。

\displaystyle
\begin{cases}
    L(2) = \infty, L(1) + w(\{1, 2\}) = 7 \\
    L(3) = \infty, L(1) + w(\{1, 3\}) = 9 \\
    L(6) = \infty, L(1) + w(\{1, 6\}) = 14 \\
\end{cases}

なので、ラベル L(2), L(3), L(6) を更新する。

step5:
集合 T から点 1 を除く。
T = \{2, 3, 4, 5, 6\}, V(G) \setminus T = \{1\}


step2:
最小のラベルを持つ点を T から探すと、ラベル L(2) = 7 である点 2 が見つかる。

step4:
2 と隣接している集合 T の点は 3, 4 である。

\displaystyle
\begin{cases}
    L(3) = 9, L(2) + w(\{2, 3\}) = 17 \\
    L(4) = \infty, L(2) + w(\{2, 4\}) = 22 \\
\end{cases}

なので、ラベル L(4) を更新する。

step5:
集合 T から点 2 を除く。
T = \{3, 4, 5, 6\}, V(G) \setminus T = \{1, 2\}


step2:
最小のラベルを持つ点を T から探すと、ラベル L(3) = 9 である点 3 が見つかる。

step4:
3 と隣接している集合 T の点は 4, 6 である。

\displaystyle
\begin{cases}
    L(4) = \infty, L(3) + w(\{3, 4\}) = 20 \\
    L(6) = 14, L(3) + w(\{3, 6\}) = 11 \\
\end{cases}

なので、ラベル L(4), L(6) を更新する。

step5:
集合 T から点 3 を除く。
T = \{4, 5, 6\}, V(G) \setminus T = \{1, 2, 3\}


step2:
最小のラベルを持つ点を T から探すと、ラベル L(6) = 11 である点 6 が見つかる。

step4:
6 と隣接している集合 T の点は 4, 5 である。

\displaystyle
\begin{cases}
    L(4) = 20, L(6) + w(\{6, 4\}) = 16 \\
    L(5) = \infty, L(6) + w(\{6, 5\}) = 10 \\
\end{cases}

なので、ラベル L(4), L(5) を更新する。

step5:
集合 T から点 6 を除く。
T = \{4, 5\}, V(G) \setminus T = \{1, 2, 3, 6\}


step2:
最小のラベルを持つ点を T から探すと、ラベル L(4) = 16 である点 4 が見つかる。

step3:
4 は到着点なので、w(1, 4) = 16 と出力して、アルゴリズムを終了する。


実装例

networkx

networkx で上記のアルゴリズムをそのまま実装した例を以下に示す。

  • G[v] でグラフ G における点 v と隣接している点をイテレータで取得できる。
  • あるエッジの重みは G.edges[v, u]["weight"] でアクセスする。
  • prev に各点にいたる重み最小の道の1つ前の点を格納する。補題1、2より1つ前の点だけ覚えておけばよいことに注意する。
import networkx as nx
import numpy as np

# グラフを定義する。
G = nx.Graph()
G.add_weighted_edges_from(
    [
        (1, 2, 7),
        (1, 3, 9),
        (1, 6, 14),
        (2, 3, 10),
        (2, 4, 15),
        (3, 4, 11),
        (3, 6, 2),
        (4, 6, 5),
        (5, 6, 9),
    ]
)


def get_path(prev, y):
    print(prev)
    path = [y]
    while prev[path[-1]]:
        path.append(prev[path[-1]])

    return list(reversed(path))


def dijkstra(G, x, y):
    """
    Args:
        G: グラフ
        x: 始点
        y: 終点
        
    Returns:
        (path, dist): 重み最小の x-y 道及びその重み
    """
    # step1:
    # ラベルを初期化する。
    L = {n: 0 if n == x else np.inf for n in G.nodes}
    # パスを初期化する。
    prev = {n: None for n in G.nodes}
    # 未確定の集合を初期化する。
    T = list(G.nodes)

    while True:
        # step2: 最小のラベルを持つ点を探す。
        v = min(T, key=lambda n: L[n])

        # step3: v == y の場合は終了する。
        if v == y:
            break

        # step4: v に隣接する点 u に対して、T の点かつ
        #        L(u) > L(v) + w(v, u) ならば、
        #        L(u) = L(v) + w(v, u) として更新する。
        for u in G[v]:
            if u in T and L[u] > L[v] + G.edges[v, u]["weight"]:
                L[u] = L[v] + G.edges[v, u]["weight"]
                prev[u] = v

        # step5: 集合 T から点 v を除く。
        T.remove(v)

    return get_path(prev, y), L[y]


d, path = dijkstra(G, x=1, y=4)
print("shortest length: {}, shortest path: {}".format(d, path))
# shortest length: [1, 3, 6, 4], shortest path: 16

networkx の関数を使う場合

import networkx as nx

# グラフを定義する。
G = nx.Graph()
G.add_weighted_edges_from(
    [
        (1, 2, 7),
        (1, 3, 9),
        (1, 6, 14),
        (2, 3, 10),
        (2, 4, 15),
        (3, 4, 11),
        (3, 6, 2),
        (4, 6, 5),
        (5, 6, 9),
    ]
)


path = nx.shortest_path(G, 1, 4, weight='weight')
dist = nx.shortest_path_length(G, 1, 4, weight='weight')
print("shortest path: {}, shortest length: {}".format(path, dist))
# shortest path: [1, 3, 6, 4], shortest length: 16

参考