Python3_朴素Dijkstra算法
作者:
成理第一深情
,
2024-01-27 20:02:21
,
所有人可见
,
阅读 49
- 在Python中
float("inf")
表示正无穷大
"""
朴素Dijkstra算法:处理稠密图问题。如题所示,当边数是点数的平方的时候采用朴素算法,因为算法时间复杂为O(N^2),与边的条数无关
具体思路:
1. 初始化:需要初始化每个点到起点的距离为正无穷,起点到起点的距离为0
2. 每次从未标记的点中选取到起点最短的点,标记,收到最短路径集合之中
3. 用第2步选取的点去更新其能到达的所有点的距离
重边的处理方式:只需要保留最短的那一条边
自环的处理方式:不需要处理,因为永远不会更新
"""
def dijkstra():
for i in range(n): # 每次只有一个点被加到最短路径集合中
t = -1
for j in range(1, n + 1): # 每次枚举所有点,找到不在集合之中且到起点最短的点
if st[j] == False and (t == -1 or dist[j] < dist[t]):
t = j
st[t] = True
# 更新刚才找到那个点所有能到达点的距离
for j in range(1, n + 1):
dist[j] = min(dist[j], dist[t] + g[t][j])
if dist[n] == float("inf"):
return False
return dist[n]
n, m = map(int, input().strip().split())
g = [[float("inf")] * (n+1) for _ in range(n+1)]
for i in range(m):
x, y, c = map(int, input().strip().split())
g[x][y] = min(g[x][y], c) # 处理重边,只保留最短的那一条
dist = [float("inf") for i in range(n+1)] # 初始化所有点到起点的距离
dist[1] = 0 # 初始化起点到起点的距离
st = [False for i in range(n+1)] # 初始化状态,表示每个点是不是已经被加到最短路径集合了
res = dijkstra()
if res:
print(res)
else:
print(-1)