ダイクストラ法 - 西尾泰和の外部脳

ダイクストラ法

最短経路を求めるアルゴリズム

次に探索すべき頂点を見つけることを優先度キューを使ってlogオーダーにする。heapq

O((E+V)log V)

code:python

def shortest_path(

start, goal, num_vertexes, edges,

INF=9223372036854775807, UNREACHABLE=-1):

distances = INF * num_vertexes

prev = None * num_vertexes

distancesstart = 0

queue = (0, start)

while queue:

d, frm = heappop(queue)

if distancesfrm < d:

# already know shorter path

continue

if frm == goal:

path = goal

p = goal

while p != start:

p = prevp

path.append(p)

path.reverse()

return d, path

for to in edgesfrm:

new_cost = distancesfrm + edgesfrmto

if distancesto > new_cost:

# found shorter path

distancesto = new_cost

prevto = frm

heappush(queue, (distancesto, to))

return UNREACHABLE

https://judge.yosupo.jp/submission/28034

old version

code:python

from collections import defaultdict

from heapq import *

# fast input

import sys

input = sys.stdin.buffer.readline

INF = sys.maxsize

num_vertexes, num_edges, start, goal = map(int, input().split())

edges = defaultdict(dict)

distances = INF * num_vertexes

distancesstart = 0

shortest_path = defaultdict(list)

shortest_pathstart = []

for i in range(num_edges):

a, b, c = map(int, input().split())

edgesab = c

# edgesba = c # if bidirectional

queue = (0, start)

while queue:

d, frm = heappop(queue)

if distancesfrm < d:

# already know shorter path

continue

if frm == goal: # goal

break

for to in edgesfrm:

if distancesto > distancesfrm + edgesfrmto:

# found shorter path

distancesto = distancesfrm + edgesfrmto

heappush(queue, (distancesto, to))

shortest_pathto = (frm, to)

if distancesgoal == INF:

# unreachable

print(-1)

else:

path = []

cur = goal

while True:

frm, to = shortest_pathcur

path.append((frm, to))

cur = frm

if frm == start:

break

path.reverse()

print(distancesgoal, len(path))

for frm, to in path:

print(frm, to)

このコードの修正点

最短パスの表示が必要でない時にどこを捨てればいいかを明確にする

パスを構成するエッジの数を出力しているが、エッジコストの和を出したい場合も多い