AcWing 849. Dijkstra求最短路 I
原题链接
简单
作者:
不知名_4
,
2024-07-25 18:28:18
,
所有人可见
,
阅读 3
迪杰斯特拉Dijkstra
Python 代码
n,m = map(int,input().split())
# 节点序号从 1 开始
edges = [[float('inf') for i in range(n+1)]for j in range(n+1)]
for i in range(m):
u,v,w = map(int,input().split())
# 可能有重复边,保留最短权值边即可——eg:1 2 2和1 2 8
if w<edges[u][v]:
edges[u][v] = w
final = [False for i in range(n+1)]
dist = [float('inf') for i in range(n+1)]
path = [-1 for i in range(n+1)]
# ----------------------------------------#
# 题目求的是 1号节点 到 n号节点 的最短距离
# 所以初始化1号节点有关信息
# ----------------------------------------#
final[1] = True
dist[1] = 0
for i in range(1,n+1):
if i!=1:
if edges[1][i] < float('inf'):
dist[i] = edges[1][i]
path[i] = 1
# path[1]保持为-1即可
while True:
# flag = False
# 寻找当前未联通,且可到达的最近节点,节点序号保存于v
cost = float('inf')
v = -1
for i in range(1,n+1):
if not final[i] and dist[i]<cost:
v = i
cost = dist[i]
if v == -1:
# 已不存在可继续连通的点
break
else:
final[v] = True
for i in range(1,n+1):
if i!=v:
if dist[v] + edges[v][i] < dist[i]:
dist[i] = dist[v] + edges[v][i]
path[i] = v # 前驱节点
# print(path) # 从1 到达n节点最短路径,途径各节点的前驱节点记录
# 如果存在一条路径从1到达n节点,那么dist[n]就不会未无穷大
if dist[n] == float('inf'):
print(-1)
else:
print(dist[n])