Robin Pourtaud - Personal Blog
ダイクストラのアルゴリズム - 例と修正
ダイクストラのアルゴリズム - 例と修正
ダイクストラのアルゴリズムは、負の重みがないグラフにおいて、ソースから他のすべての頂点への最短経路を探索するアルゴリズムです。
By Robin Pourtaud on

アルゴリズム

推奨事項

最短経路アルゴリズムにまだ慣れていない場合は、ベルマンフォードアルゴリズムのようなもう少し簡単なアルゴリズムから始めるべきです。ベルマンフォードアルゴリズムの説明はこちらで見つけることができます。

def dijkstra(G: Graph, p:function(int,int) -> int, source: int) -> [prev: List[int], weight: List[int]]:
    '''ダイクストラの擬似コード。

    引数: 
        G : Graph : 負のサイクルがないグラフ
        p : function(int, int) -> int : 辺 (u, v) の重みを O(1) で返す関数。例: p(1,2) は辺 (1,2) の重みを返す
        source : int : V におけるソース頂点のインデックス
    
    戻り値:
        prev : List[int] : 各頂点の前の頂点を含む配列。
        weight : List[int] : 各頂点について、ソースからその頂点までの最短経路の重み（重みの合計）を含む配列。
    '''

    # 初期化
    for v in G.vertices:
        weight[v] = inf
        prev[v] = '-'

    weight[source] = 0 # ソースからソースへの重みは0

    Q = G.vertices # すべての頂点

    while Q != {}: # Qが空でない間
        temp = inf
        minQ = -1
        for q in Q:
            if weight[q] < temp:
                temp = weight[q]
                minQ = q
        Q.remove(minQ)
        for q_prime in G.successors(minQ):
            if weight[q_prime] > weight[minQ] + p(minQ, q_prime):
                weight[q_prime] = weight[minQ] + p(minQ, q_prime)
                prev[q_prime] = minQ

    return prev, weight

正の重みのみ

このアルゴリズムは正の重みを持つグラフにのみ適用されます！グラフに負の重みが含まれている場合（ただし、負の重みのサイクルはない場合）、ベルマンフォードアルゴリズムを使用できます。

ベルマンフォードの複雑さは であるのに対し、ダイクストラのアルゴリズムは優先度キューを使用すると または です。

以下は、ダイクストラのアルゴリズムが適用されないグラフの簡単な例です：

Diagram

ダイクストラは、Bの重みが4であるため、AからCへの重み1の経路を選択します。しかし、最短経路はAからBを経由してCへの重み-1の経路です。

例

ここに2つの有向グラフがあります。

  1. これらのグラフにダイクストラのアルゴリズムを使用して、s から t までの最短経路を見つけることができますか？
  2. もしできるなら、ダイクストラのアルゴリズムを使用して s から t までの最短経路を決定してください。

例1:

Diagram

辺が交差していることをお詫びします。配置は自動です。

解決策 1

グラフ内の辺の1つに負の重みが関連付けられています。したがって、ダイクストラのアルゴリズムはここでは適用されません。ベルマンフォードアルゴリズム（または他のアルゴリズム）を使用する必要があります。

例2:

Diagram

解決策 2

2つの表を組み合わせることもできます。例えば、各セルに “重み/前” と記入することができます。

重み表

ステップs012345t
初期化0
Q -= s/642
Q -= 3/64/
Q -= 1/6//6
Q -= 0///9/6
Q -= 4///9//7
Q -= 5///8///
Q -= 2///////11
Q -= t////////

この表を理解するためのヒント：

  1. 初期化: 最初に、ソース頂点が自身からの距離が0であることだけがわかっています。他は不明なので、を入れます。
  2. 次のステップ: 既知の頂点（ここではソースのみ）から、最小の重みを持つ頂点の後続を見ます。記録された値より小さい場合は、後続への距離を設定します。前の頂点の表も同時に更新することを忘れないでください。
  3. Q -=: 重みが最小の頂点をQから削除します。このステップでは、頂点sを削除します。
  4. 読みやすさのためのヒント: 頂点がQにもうない場合、セルに ”/” を入れます。上の数字は頂点の実際の重みです。
  5. アルゴリズムの終了: Qが空になったとき、最後にの重みを読み取ることができます。

前の頂点表

ステップs012345t
初期化--------
Q -= s/ss-s---
Q -= 3/ss-/---
Q -= 1/s/-/1--
Q -= 0///0/1--
Q -= 4///0//4-
Q -= 5///5///-
Q -= 2///////2
Q -= t////////

S から T までの最短経路を見つけましょう：

  • t の前の頂点は 2
  • 2 の前の頂点は 5
  • 5 の前の頂点は 4
  • 4 の前の頂点は 1
  • 1 の前の頂点は s

したがって、s から t までの最短経路は次の通りです：

合計の重みは: