ダイクストラ法
最短経路を求めるアルゴリズム
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 while queue:
d, frm = heappop(queue)
# already know shorter path
continue
if frm == goal:
p = goal
while p != start:
path.append(p)
path.reverse()
return d, path
if distancesto > new_cost: # found shorter path
heappush(queue, (distancesto, to)) return UNREACHABLE
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 shortest_path = defaultdict(list)
for i in range(num_edges):
a, b, c = map(int, input().split())
# edgesba = c # if bidirectional while queue:
d, frm = heappop(queue)
# already know shorter path
continue
if frm == goal: # goal
break
# found shorter path
heappush(queue, (distancesto, to)) shortest_pathto = (frm, to) # 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)
このコードの修正点
最短パスの表示が必要でない時にどこを捨てればいいかを明確にする
パスを構成するエッジの数を出力しているが、エッジコストの和を出したい場合も多い