【算法】【Python】邻接表和迪杰斯特拉Dijkstra算法求解单源最短路径问题

import sys
import heapq

def dijkstra(n, m, edges):
    INF = float('inf')
    graph = [[] for _ in range(n + 1)]  # 邻接表
    
    # 读取图的边信息
    for u, v, w in edges:
        graph[u].append((v, w))
    
    # 初始化距离数组
    dist = [INF] * (n + 1)
    dist[1] = 0  # 皇宫（起点）
    
    # 优先队列（小根堆）
    pq = [(0, 1)]  # (距离, 节点)
    
    while pq:
        d, u = heapq.heappop(pq)
        
        if d > dist[u]:
            continue  # 已经更新过更短的路径
        
        for v, w in graph[u]:
            if dist[v] > d + w:
                dist[v] = d + w
                heapq.heappush(pq, (dist[v], v))
    
    return ' '.join(str(dist[i]) if dist[i] != INF else "-1" for i in range(1, n + 1))

# 读取 N, M
N, M = map(int, input().strip().split())

# 读取边信息
edges = [tuple(map(int, input().strip().split())) for _ in range(M)]
print(edges)
# 计算并输出结果
print(dijkstra(N, M, edges))

算法步骤：

• 使用邻接表存储图，以减少内存占用和加快访问速度。
• 使用heapq作为优先队列，每次弹出当前最近的节点，避免不必要的计算。
• dist 数组存储最短路径，初始值设为无穷大 (INF)，起点 dist[1] = 0。
• 循环中更新最短路径，若 dist[v] > d + w，则更新 dist[v] 并将其加入堆。
• 输出处理，不可达的点输出 -1，否则输出最短距离。