アルゴリズム

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

正の重みのみ

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

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

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

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

例

例1:

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

解決策 1

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

例2:

解決策 2

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

重み表

前の頂点表

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

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

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