ダイクストラ法

放送大学の問題解決の数理で学んだアルゴリズムの覚書。

ダイクストラ法とは
計算量
処理概要
ソースコード
定式化
- 定式化例題
参考

ダイクストラ法とは

2頂点間の最短距離を求める。

重みがマイナスだと使えない。

計算量

O(頂点数²) （オリジナルの場合）

O((頂点数＋辺の数）* log頂点数) (優先度付きキューの場合）

※厳密な計算量はWikipediaを参考にすること。

処理概要

全ての頂点に、始点からの距離無限大を仮で書き込む。（初期化）
始点に、始点からの距離０を書き込む。（初期化）
次に行ける頂点に対して、始点からの距離を計算、現在書き込まれている距離より短ければ更新する。
始点からの距離が最も小さい＆未訪問の頂点を選び、その頂点に行く。
未訪問頂点がまだあれば、３～４を繰り返す。
すべての頂点が訪問済になったら終了。

ソースコード

N=6
visited=[False]*N
#始点からの距離。初めは全頂点に無限値にする
startFromDistance=[math.inf]*N 

#(頂点番号,重み)のタプルを持つグラフ
G=[[(1,1),(2,5)]
   ,[(0,1),(2,4),(3,2)]
   ,[(0,5),(1,2),(4,2)]
   ,[(2,3),(5,3)]
   ,[(2,1),(5,4)]
   ,[]]

def dijkstra(G, vertex):
  heap=[(0,0)]#重み、頂点番号（優先度付きキュー。最も重みの軽い頂点から優先で取り出す）
  startFromDistance[0] = 0

  while len(heap) > 0:
    distance, now = heapq.heappop(heap)
    
    if visited[now]:
      continue
    visited[now] = True

    for next, weight in G[now]:
      if visited[next]:
        continue

      # nowから到達可能な頂点の距離更新
      newDistance = startFromDistance[now] + weight
      if newDistance < startFromDistance[next]:
        startFromDistance[next] = newDistance

        #次の行き先候補を格納
        heapq.heappush(heap, (newDistance, next))
  return startFromDistance

print(dijkstra(G, 0)) #[0, 1, 5, 3, 7, 6]