dijkstra 算法思路
咱直接说优化后的思路,其实就是用到了小顶堆(优先级队列)来比较哪一个点的距离最近,关于堆排序,可以参考堆的实现及工程应用。...从起点 s 开始,将与起点 s 直接相连的点,根据它与起点 s 的距离,加入到小顶堆中,堆顶那个点 s1 与起点 s 的距离 d1 一定是最近的,取出堆顶的点 s1 ,然后把与 s1 直接相连的点,根据它与...s 的距离(d1 + s1到这个点的距离),加入到小顶堆中,堆顶那个点 s2 与起点的距离就是最小的。...[-1, -1, -1, 6, 0, 9],
[14, -1, 2, -1, 9, 0],
]
cost = [max] * vertices_number
pq = [] # 优先级队列...:
# printpq(pq)
# 出队
node = heapq.heappop(pq)
from_vertex1 = node.vertex