ダイクストラ法をPythonで

ダイクストラ法

最短経路問題に対する解法

辺の重みに負がないときに限る。

計算量は隣接行列を用いた場合O(|V²|) heap で処理するとO(|E|log|V|)

from heapq import * 

q = []

# heapq.heapify(q)

inf = float("INF")

def djk(start_node,num_node):
  dist = [inf]*num_node
  queqe = [(0,start_node)]
  dist[start_node] = 0
  used = [False] * num_node

  while queqe:
    frm = heappop(queqe)[1]
    used[frm] = True
    for to, cost in adj[frm]:
      if used[to] == False and dist[frm] + cost < dist[to]:
        dist[to] = dist[frm] + cost
        heappush(queqe,(dist[to],to))
  
  return dist

# ノード数, エッジ数, 始点ノード
v, e= map(int, input().split())
# adj[s]: ノード s に隣接する(ノード, 重み)をリストで持つ
adj = [[] for _ in range(v)]
for i in range(e):
    s, t, d = map(int, input().split())
    s-=1
    t-=1
    adj[s].append((t, d))
    adj[t].append((s, d))
m = inf
for start in range(v):
    d = djk(start,v)
    m = min(m,max(d))
    # print(d)
print(m)

https://atcoder.jp/contests/abc012/tasks/abc012_4

両方向に辺をはる。 辺の数が少ないため始点を変えてすべて試す。 それぞれのリストの最大値をとり その中の最小値を出力

from heapq import * 

q = []

# heapq.heapify(q)

inf = float("INF")

def djk(s_node,num_node):
  d = [inf]*num_node
  q = [(0,s_node)]
  d[s_node] = 0
  used = [False] * num_node

  while q:
    frm = heappop(q)[1]
    used[frm] = True
    for to, cost in adj[frm]:
      if used[to] == False and d[frm] + cost < d[to]:
        d[to] = d[frm] + cost
        heappush(q,(d[to],to))
  
  return d

# ノード数, エッジ数, 始点ノード
v, e= map(int, input().split())
# adj[s]: ノード s に隣接する(ノード, 重み)をリストで持つ
adj = [[] for _ in range(v)]
for i in range(e):
    s, t, d = map(int, input().split())
    s-=1
    t-=1
    adj[s].append((t, d))
    adj[t].append((s, d))
m = inf
for start in range(v):
    d = djk(start,v)
    m = min(m,max(d))
    # print(d)
print(m)

参考サイト

https://mirucacule.hatenablog.com/entry/2020/05/21/124026