正在展开冲刺页面
正在展开冲刺页面
堆优化最短路，边权为非负时间或距离。
邻接表。
起点到各点距离。
配送、校园步行、应急路线。
完整可运行代码
import heapq
graph = {0: [(1, 2), (2, 5)], 1: [(2, 1), (3, 3)], 2: [(3, 2)], 3: []}
def dijkstra(start):
dist = {start: 0}
pq = [(0, start)]
while pq:
d, u = heapq.heappop(pq)
if d != dist[u]:
continue
for v, w in graph[u]:
nd = d + w
if nd < dist.get(v, 1e18):
dist[v] = nd
heapq.heappush(pq, (nd, v))
return dist
print(dijkstra(0))