問題定義

エッジが重みを持つグラフ構造において、ある頂点から別の頂点への最短経路を求めたい。
ただし、各エッジの重みは0以上（通ることでコストが下がる経路は存在しない） とする。

※ 負の重みを持つ場合、グラフが有向グラフであればベルマンフォード法を適用できる。

アルゴリズム

具体例をもとに手順を解説する。
以下のグラフにおいて A から各ノードへの最短経路を求める。

図0

【0】変数の初期化

以下の変数を準備して初期化。

変数 内容 初期値
shortest_weight 「現時点で判明している」A から各ノードまでの最短距離を保持する辞書 $\infty$
shortest_path 「現時点で判明している」A から各ノードまでの最短パスを保持する辞書 null
n_last_fix 最新ステップで最短経路が確定したノード null

図1

shortest_weight = {
    'A': float('inf'),
    'B': float('inf'),
    ...,
    'F': float('inf')
}

shortest_path = {
    'A': None,
    'B': None,
    ...,
    'F': None
}

n_last_fix = None

【1】スタート地点自身までの最短経路を確定

スタート地点 A 自身までの最短距離が0であるのは明らかなので、A までの最短距離と経路を確定させる：

  • shortest_weight['A'] = 0 (Fix)
  • shortest_path['A'] = ['A'] (Fix)
  • n_last_fix = 'A'

図2

shortest_weight = {
    'A': 0,             # fixed
    'B': float('inf'),
    'C': float('inf'),
    'D': float('inf'),
    'E': float('inf'),
    'F': float('inf')
}

shortest_path = {
    'A': ['A'],         # fixed
    'B': None,
    'C': None,
    'D': None,
    'E': None,
    'F': None
}

n_last_fix = 'A'  # updated

【2】最後に確定したノードの隣接ノードの情報を更新

最短経路が未確定のノードのうち、n_last_fix の隣接ノード n_next それぞれについて、以下のルールで shortest_weight, shortest_path を更新する

  • $d_\mathrm{old}$：現時点でわかっているスタートからそのノードまでの最短距離 shortest_weight[n_next]
  • $d_\mathrm{new}$：以下の2つの和
    • 確定済みの n_last_fix までの最短距離shortest_weight[n_last_fix]
    • n_last_fix から n_next までの距離
  • $d_\mathrm{new} \lt d_\mathrm{old}$ なら最短距離・最短経路を更新：
    • shortest_weight[n_next] = d_new
    • shortest_path[n_next] = shortest_path[n_last_fix] + n_next
shortest_weight = {
    'A': 0,             # (fixed)
    'B': 7,             # updated
    'C': 4,             # updated
    'D': 2,             # updated
    'E': float('inf'),
    'F': float('inf')
}

shortest_path = {
    'A': ['A'],         # (fixed)
    'B': ['A', 'B'],    # updated
    'C': ['A', 'C'],    # updated
    'D': ['A', 'D'],    # updated
    'E': None,
    'F': None
}

n_last_fix = 'A'

【3】未確定のうち距離が一番小さいノードの距離・経路を確定

最短経路が未確定のノードを全て見て、現時点の距離が一番小さいノードの距離と経路を fix（他のルート経由では、絶対にこれより長くなる）

今回の例だと shortest_weight['D'] の2が最小なので D を fix。
よって n_last_fix = 'D'

図3

shortest_weight = {
    'A': 0,             # (fixed)
    'B': 7,
    'C': 4,
    'D': 2,             # (fixed)
    'E': float('inf'),
    'F': float('inf')
}

shortest_path = {
    'A': ['A'],         # (fixed)
    'B': ['A', 'B'],
    'C': ['A', 'C'],
    'D': ['A', 'D'],    # (fixed)
    'E': None,
    'F': None
}

n_last_fix = 'D'  # updated

【4】2,3を繰り返し

n_last_fix が更新されなくなるまで2,3を繰り返す。

図4

shortest_weight = {
    'A': 0,              # (fixed)
    'B': 7,
    'C': 4,              # [1]not updated --> [2]fixed
    'D': 2,              # (fixed)
    'E': float('inf'),
    'F': 8               # [1]updated
}

shortest_path = {
    'A': ['A'],          # (fixed)
    'B': ['A', 'B'],
    'C': ['A', 'C'],     # [1]not updated --> [2]fixed
    'D': ['A', 'D'],     # (fixed)
    'E': None,
    'F': ['A', 'D', 'F'] # [1]updated
}
n_last_fix = 'C'  # updated

図5

shortest_weight = {
    'A': 0,             # (fixed)
    'B': 6,             # [1]updated --> [2]fixed
    'C': 4,             # (fixed)
    'D': 2,             # (fixed)
    'E': float('inf'),
    'F': 6              # updated
}

shortest_path = {
    'A': ['A'],           # (fixed)
    'B': ['A', 'C', 'B'], # [1]updated --> [2]fixed
    'C': ['A', 'C'],      # (fixed)
    'D': ['A', 'D'],      # (fixed)
    'E': None,
    'F': ['A', 'C', 'F']  # [1]updated
}

# B, F は最短距離が同じなので、どちらを先に fix しても良い. ここでは B を選択
n_last_fix = 'B'  # updated

図6

shortest_weight = {
    'A': 0,             # (fixed)
    'B': 6,             # (fixed)
    'C': 4,             # (fixed)
    'D': 2,             # (fixed)
    'E': 12,            # [1]updated
    'F': 6              # [1]not updated --> [2]fixed
}

shortest_path = {
    'A': ['A'],                # (fixed)
    'B': ['A', 'C', 'B'],      # (fixed)
    'C': ['A', 'C'],           # (fixed)
    'D': ['A', 'D'],           # (fixed)
    'E': ['A', 'C', 'B', 'E'], # [1]updated
    'F': ['A', 'C', 'F']       # [1]not updated --> [2]fixed
}

n_last_fix = 'F'  # updated

図7

shortest_weight = {
    'A': 0,             # (fixed)
    'B': 6,             # (fixed)
    'C': 4,             # (fixed)
    'D': 2,             # (fixed)
    'E': 10,            # [1]updated --> [2]fixed
    'F': 6              # (fixed)
}

shortest_path = {
    'A': ['A'],                # (fixed)
    'B': ['A', 'C', 'B'],      # (fixed)
    'C': ['A', 'C'],           # (fixed)
    'D': ['A', 'D'],           # (fixed)
    'E': ['A', 'C', 'F', 'E'], # [1]updated --> [2]fixed
    'F': ['A', 'C', 'F']       # (fixed)
}

n_last_fix = 'E'  # updated

→ 全てのノードが fix され、これ以降は繰り返しても n_last_fix は更新されない。
→ このときのshortest_pathとshortest_weightが、求める最短経路とその重み。

図8

実装・動作確認

実装

動作確認

前述の「処理の流れ」で扱ったグラフのとき：

Graph gv

>>> dijkstra(graph, 'A')
from A to A: weight=0, path=['A']
from A to B: weight=6, path=['A', 'C', 'B']
from A to C: weight=4, path=['A', 'C']
from A to D: weight=2, path=['A', 'D']
from A to E: weight=10, path=['A', 'C', 'F', 'E']
from A to F: weight=6, path=['A', 'C', 'F']

>>> dijkstra(graph, 'C')
from C to A: weight=4, path=['C', 'A']
from C to B: weight=2, path=['C', 'B']
from C to C: weight=0, path=['C']
from C to D: weight=3, path=['C', 'D']
from C to E: weight=6, path=['C', 'F', 'E']
from C to F: weight=2, path=['C', 'F']

ツリー状である時

Graph02

graph = {
    # from, to, weight
    ('A', 'B', 5),
    ('A', 'C', 4),
    ('A', 'D', 2),
    ('B', 'E', 6),
    ('B', 'F', 7),
    ('C', 'G', 3),
    ('C', 'H', 2)
}
show_graph(graph)

>>> dijkstra(graph, 'A')
from A to A: weight=0, path=['A']
from A to B: weight=5, path=['A', 'B']
from A to C: weight=4, path=['A', 'C']
from A to D: weight=2, path=['A', 'D']
from A to E: weight=11, path=['A', 'B', 'E']
from A to F: weight=12, path=['A', 'B', 'F']
from A to G: weight=7, path=['A', 'C', 'G']
from A to H: weight=6, path=['A', 'C', 'H']

>>> dijkstra(graph, 'E')
from E to A: weight=11, path=['E', 'B', 'A']
from E to B: weight=6, path=['E', 'B']
from E to C: weight=15, path=['E', 'B', 'A', 'C']
from E to D: weight=13, path=['E', 'B', 'A', 'D']
from E to E: weight=0, path=['E']
from E to F: weight=13, path=['E', 'B', 'F']
from E to G: weight=18, path=['E', 'B', 'A', 'C', 'G']
from E to H: weight=17, path=['E', 'B', 'A', 'C', 'H']

グラフが分断されている時

Graph03

graph = {
    # from, to, weight
    ('A', 'B', 5),
    ('A', 'C', 2),
    ('A', 'D', 7),
    ('B', 'C', 2),
    ('C', 'D', 1),
    ('E', 'F', 4),
    ('F', 'G', 1)
}
show_graph(graph)

>>> dijkstra(graph, 'A')
from A to A: weight=0, path=['A']
from A to B: weight=4, path=['A', 'C', 'B']
from A to C: weight=2, path=['A', 'C']
from A to D: weight=3, path=['A', 'C', 'D']
from A to E: weight=inf, path=None
from A to F: weight=inf, path=None
from A to G: weight=inf, path=None

>>> dijkstra(graph, 'E')
from E to A: weight=inf, path=None
from E to B: weight=inf, path=None
from E to C: weight=inf, path=None
from E to D: weight=inf, path=None
from E to E: weight=0, path=['E']
from E to F: weight=4, path=['E', 'F']
from E to G: weight=5, path=['E', 'F', 'G']

計算量

  • 1回のループで最短経路が1つ確定するので、ノード数を $V$ とすると、このループを $V$ 回繰り返す必要があるため、その計算量は $O(V)$
  • また、1つの最短経路が確定すると、そのノードから接続された隣接ノードまでの距離を更新する必要があり、隣接ノードは最大で $V-1$ 個あるため、この計算量も $O(V)$

以上により、ダイクストラ法の計算量は $O(V^2)$ となる。

※ 優先度付きキューを利用する改良版だと、$O((E+V) \log V)$（$E$ はエッジ数）に削減できるらしい（要調査）

import itertools
import datetime
import random
import numpy as np
from matplotlib import pyplot as plt

def gen_graph(n_node, n_edge):
    nodes = np.arange(n_node)
    pairs = np.array(list(itertools.combinations(nodes, 2)))
    idx = np.random.choice(range(len(pairs)), n_edge, replace=False)
    graph = set()
    for f, t in pairs[idx]:
        graph.add((f, t, np.random.rand()))
    return graph

def simulate_various_n_edge(T=10):
    plt.figure(figsize=(9, 8))
    plt.subplots_adjust(wspace=0.4, hspace=0.6)
    ns_node = [100, 400, 1000]
    for i in range(len(ns_node)):
        n_node = ns_node[i]
        ns_edge = [int(n) for n in np.linspace(n_node, n_node*(n_node-1)/4, 10)]
        dt_mean, dt_std = [], []
        for n_edge in ns_edge:
            buff = []
            for _ in range(T):
                graph = gen_graph(n_node, n_edge)
                n_start = random.choice([f for f, _, _ in graph])
                start = datetime.datetime.now()
                dijkstra(graph, n_start)
                buff.append((datetime.datetime.now()-start).total_seconds())
            dt_mean.append(np.mean(buff))
            dt_std.append(np.std(buff))
        plt.subplot(len(ns_node), 1, i+1)
        plt.title(r'$N_={}$'.format(n_node))
        plt.errorbar(ns_edge, dt_mean, dt_std, color='black')
        plt.scatter(ns_edge, dt_mean)
        plt.grid()
        if i == len(ns_node)//2:
            plt.ylabel('Time [seconds]')
        elif i == len(ns_node)-1:
            plt.xlabel(r'$N_$')
    plt.show()

def simulate_complete_graph(T=10):
    ns_node = [int(n) for n in np.linspace(100, 1000, 10)]
    dt_mean, dt_std = [], []
    for n_node in ns_node:
        buff = []
        for _ in range(T):
            graph = gen_graph(n_node, int(n_node*(n_node-1)/2))
            n_start = random.choice([f for f, _, _ in graph])
            start = datetime.datetime.now()
            dijkstra(graph, n_start)
            buff.append((datetime.datetime.now()-start).total_seconds())
        dt_mean.append(np.mean(buff))
        dt_std.append(np.std(buff))
    plt.errorbar(ns_node, dt_mean, dt_std, color='black')
    plt.scatter(ns_node, dt_mean)
    plt.xlabel(r'$N_$')
    plt.ylabel('Time [seconds]')
    plt.grid()
    plt.show()

ノード数固定でエッジ数を変化させる：

Figure_2

完全グラフ（全てのノードが全ての他のノードとエッジで接続）のノード数を変化させる：

Figure_1