SE Can't Code

A Tokyo based Software Engineer. Not System Engineer :(

ダイクストラ法で最良優先探索。

グラフにおける単一始点の最短経路をダイクストラ法で求める。
ダイクストラ法は、辺の重みが全て同一の非負数の場合にグラフ上の2頂点間の最短経路を求めるアルゴリズムである。

擬似コード


Shortest disntances from V: # V is a Top Node.
dinstances to V is 0 for initialize.
all other distances are unknown.
while not all nodes complete:
    W = shortest known distance
    mark W which is known (lock it down)
    for all neighbor > X of W:
        if distance to W + weight(W,X) < known distance to X:
             update X's distance

ソースコード


結果


$ python dijkstra.py 
Graph : {'A': {'C': 3, 'B': 15, 'D': 4}, 'C': {'A': 3, 'B': 10}, 'B': {'A': 15, 'C': 10, 'D': 9, 'F': 1}, 'E': {'D': 3, 'G': 1, 'F': 5}, 'D': {'A': 4, 'B': 9, 'E': 3, 'F': 7}, 'G': {'E': 1, 'F': 2}, 'F': {'B': 1, 'E': 5, 'D': 7, 'G': 2}}
Result : {'A': 0, 'C': 3, 'B': 11, 'E': 7, 'D': 4, 'G': 8, 'F': 10}


ダイクストラ法の計算量は { \displaystyle
θ(n^2)
} になる。また、ダイクストラ法は最小である頂点を取り除いていくヒープと相性が良いために、ヒープを使うと計算量が減る。

for each node:
    1. find the shortest dist-so-far
    2. remove it
    3. check each of its neighbors possibly reducing distance


上記擬似コードの1.については { \displaystyle
θ(n \log n)
}の計算量となり、3.については { \displaystyle
θ(m \log n)
}となるため、加算をするとヒープを用いたトータルの計算量は { \displaystyle
θ(m \log n)
}となる。 このようにダイクストラ法を用いると、頂点となるノードとゴールとなるノードの最短距離を求めることが可能となる。ダイクストラ法自体がやっていることはシンプルで、最小となる距離を各ノードを繋ぐエッジに対して出して更新をかけてることを全ノードに対して行うといった、重みつきグラフの二点間の最短経路を把握する際に利用できる。


現場からは以上です。

参考