ダイクストラ法

ダイクストラ法とは、グラフ中のどのエッジもそこを通るコストが0以上であるときに、ある始点ノードからある終点ノードに至る経路でコストが最小のものを特定できるアルゴリズムである。エッジのコストは通る向きによって異なってもよい。通るコストが負のエッジがあってはならない。

参考文献

Dijkstra's Algorithm. (2024年11月2日参照).

ダイクストラ法

右図のノード0からノード8までの最小コスト経路を求めることを考えます。方針として、ノード0からの最小コストが確定するノードから確定させていきます。まず、ノード0自身はノード0からの最小コストが0であることがただちに確定します (コストが負のエッジはないので、あえて他のノードを巡ってきた方がコストが小さくなるということはありません)。次に、確定したノード0から直結するノードについて、ノード0から直行したときのコストを暫定コストとしてメモします。
そうすると、暫定コストのうち最小値をもっているノード3については、ノード0からの最小コストがそれで確定します。なぜなら、ノード3の暫定コストはノード0からの直行時のコストでしたが、もしノード0からノード3まで直行しないならばノード1かノード2を通らなければならず、そうするとノード1かノード2に到達した時点でノード3への直行コストよりコストが大きいからです。
次に、確定したノード3から直結するノードについて、ノード3から直行したときのコストを暫定コストとしてメモします (ノード2には既にノード0から直行時の暫定コストがあるので横に付け足しておきます) (もっとも、既にあるコストの方が小さいので付け足す意味はありません)。そうすると、暫定コストのうち最小値 (5 の方) をもっているノード2については、最小コストがそれで確定します。なぜなら、ノード2に至る他の経路は必ず、現在暫定コストがメモされているノードをその暫定コストで通過するため、現在のノード2の暫定コストより大きくなるからです。


import queue

def load_question(filename='data.txt'):
    ifile = open(filename, encoding='utf8')
    n_nodes, n_edges = [int(v) for v in ifile.readline().split()]
    g = [{} for i in range(n_nodes)]
    for _ in range(n_edges):
        i_0, i_1, cost = [int(v) for v in ifile.readline().split()]
        g[i_0][i_1] = g[i_1][i_0] = cost
    i_start, i_end = [int(v) for v in ifile.readline().split()]
    ifile.close()
    return g, i_start, i_end

def get_path(via, i_start, i_end):
    path = [i_end]
    i = i_end
    while i != i_start:
        i = via[i]
        path.append(i)
    return path[::-1]

def dijkstra(g, i_start, i_end):
    """
    g: 各ノードから直接行けるノードおよびそのコスト
       Ex. [{1: 10, 2: 5, 3: 1}, {0: 10, 2: 4, 4: 10, 6: 3}, ... ] 
    """
    fixed = {}  # スタートからのコストが確定したノードおよびコスト
    via = {}  # そのノードにどこから来たか (経路逆算用)
    q = queue.PriorityQueue()
    q.put((0, i_start, None))  # (コスト、ノード、どこから) の3つ組
    while q.empty() == False:
        cost, i, prev = q.get()
        if i in fixed:
            continue
        fixed[i] = cost
        via[i] = prev
        if i == i_end:
            return cost, get_path(via, i_start, i_end)
        for j in g[i]:
            if j not in fixed:
                q.put((cost + g[i][j], j, i))

g, i_start, i_end = load_question()
dijkstra(g, i_start, i_end)