最短経路アルゴリズムの理解:Dijkstra

最短経路のアルゴリズムにもいろいろある。

その中でもダイクストラのアルゴリズムについて、理解した内容をまとめてみる。

基本戦略

1. いま注目してる頂点に隣接する頂点をみる
2. 隣接頂点が持つコスト(初期値はINF)と、いま注目している頂点のコスト+隣接頂点までのコスト(更新コスト)とを比較する 2-1. 更新コストが、隣接頂点が持つコストより小さかったら、隣接頂点のコストを更新コストで更新する
3. 全長頂点中、まだ最小値が確定していない頂点の内、最小のコストを持たない頂点を次の探査対象にして、1.にもどる

こんなところ。

ネットを調べればもっとまともな解説が落ちてます。 厳密orわかりやすいものを求める人は、検索してください。

入力について

以降、アルゴリズムの説明に入ります。

基本型と効率型を載せますが、どちらも入力は以下の様な感じ。

# |V| |E| s
5 7 0
# V_prev V_next Cost
1 2 7
1 3 4
1 4 3
2 3 1
2 5 2
3 5 6
4 5 5

基本型

if __name__ == '__main__':
    Vn, En, r = mulinputs()
    G = [None] * Vn
    for _ in range(En):
        vp, vn, cost = mulinputs()
    if not G[vp]:
            G[vp] = []
    G[vp].append((vn, cost))

    # INFで初期化  
    v_cost = [INF] * Vn
    # 開始頂点はコスト0
    v_cost[r] = 0

    # Queue.queueよりもcollections.dequeのほうが速いし安定してる
    q = deque()
    q.append(r)
    dones = [False] * Vn
    while q:
        current = q.popleft()
        if visited[current]:
            continue
        dones[current] = True

        for v, e in G[current] or []:
            if v_cost[current] + e >= v_cost[v]:
                continue
            v_cost[v] = v_cost[current] + e

    # (☆１)まだ最小コストが確定していない頂点の中から
    # コストが最小のものを選ぶ
        min_cost = INF
        next_v = -1  # 0はFalseと混同するので使わない
        for v in range(Vn):
            if dones[v]:
                continue
            if min_cost > v_cost[v]:
                min_cost = v_cost[v]
                next_v = v
        if next_v >= 0:
            q.append(next_v)

    # 結果を出力する
    for cost in v_cost:
        if cost < INF:
            print(cost)
        else:
            print('INF')

☆１：なぜ最小コストの頂点なのか

隣接頂点のコストを更新する際に、自身のコストを使用する。

このとき、自身の頂点のコストが最小でない場合、後続の処理でコストが更新される可能性がある。

更新されてしますと、更新した隣接頂点のコストも更新する必要があって効率が悪い。

（ほかにも、「最短経路」を求めるのに隣接頂点のコストが「最短」でなくなってしまう）

効率型

優先度付きキューを使う。

そうすると、基本型であった「すべての頂点からコストが最小のものを選ぶ」部分を省略できる。

「すべての頂点からコストが最小のものを選ぶ」部分は、線形なのでO(N)の時間計算量がかかっていた。

優先度付きキューを使うことで、この時間計算量がO(logN)に改善することができる。

（優先度付きキューは、ヒープで実装されているみたい）

また、優先度付きキューを使うと、ソースの見た目が基本型とがらっと変わる。

ミソは、(cost, vertex)の順番でキューにデータを突っ込んでいくこと。

heapqでヒープを作るとき、デフォルトで第0番目のデータを使うみたいだから。 (この場合はcost)

ここのJudgeでTLEを喰らって頑張って効率型を書いた。ドチャクソ速くなった。 （9.0秒→0.1秒ぐらい）

参考

• https://gist.github.com/kachayev/5990802
• https://qiita.com/takayg1/items/eed6d84506cc3941ae8d

    Vn, En, r = mulinputs()
    G = [None] * Vn
    for _ in range(En):
        v1, v2, cost = mulinputs()
        if not G[v1]:
            G[v1] = []
            G[v1].append((cost, v2))

    v_cost = [INF] * Vn
    v_cost[r] = 0

    # ヒープにするキュー（リスト）
    # 最小コストで並べ替えたいから、(コスト, 頂点)の順に定義する
    q = [(0, r)]
    dones = [False] * Vn
    while q:
        cost, v1 = heapq.heappop(q)
        if dones[v1]:
            continue
        dones[v1] = True
    # 隣接する頂点更新だけで十分
    # 優先度付きキューを使ってるから、
    # 最小コストの頂点を見つけるためにループを回さなくていい
        for c2, v2 in G[v1] or []:
            before_cost = v_cost[v2]
            after_cost = cost + c2
            if before_cost > after_cost:
                v_cost[v2] = after_cost
                heapq.heappush(q, (before_cost, v2))
        
    for cost in mins:
        if cost < INF:
            print(cost)
        else:
            print('INF')