Python 算法：Dijkstra 最短路径算法（Dijkstra Algorithm）

# /*
# Python 算法：Dijkstra 最短路径算法（Dijkstra Algorithm）
# --------------------------------------------------------
# 原理：
# Dijkstra 是一种贪心算法，用于求解带权非负图的单源最短路径问题。
#
# 基本思想：
# 1) 起点距离设为 0，其余设为无穷大；
# 2) 每一步从“未确定最短距离”的节点中选出距离最小的节点；
# 3) 使用该节点更新相邻节点的距离；
# 4) 重复操作直到所有节点都被确定最短路径。
#
# 使用前提：
# - 图中所有边的权值必须 >= 0
# - 适用于单源到所有点的最短路径问题
# */

import sys
import heapq

# --------------------------------------------------------
# 示例图（邻接表表示）
# 每个元素形如：graph[u] = [(v, weight), ...]
graph = [
    [(1, 2), (2, 5)],        # 0 号节点
    [(0, 2), (2, 4), (3, 6)],# 1
    [(0, 5), (1, 4), (3, 2)],# 2
    [(1, 6), (2, 2)]         # 3
]

# --------------------------------------------------------
# Dijkstra 算法实现
def dijkstra(graph, start):
    num_vertices = len(graph)
    dist = [sys.maxsize] * num_vertices   # 最短距离数组
    prev = [None] * num_vertices          # 前驱节点
    dist[start] = 0                       # 起点距离设为 0

    pq = [(0, start)]                     # 优先队列（最小堆）

    while pq:
        cur_dist, u = heapq.heappop(pq)

        # 若弹出的元素不是当前最优解，则跳过（堆中过期数据）
        if cur_dist != dist[u]:
            continue

        # 遍历相邻节点
        for v, weight in graph[u]:
            new_dist = cur_dist + weight
            if new_dist < dist[v]:
                dist[v] = new_dist
                prev[v] = u
                heapq.heappush(pq, (new_dist, v))

    return dist, prev

# --------------------------------------------------------
# 工具函数：恢复最短路径
def get_path(prev, target):
    path = []
    while target is not None:
        path.append(target)
        target = prev[target]
    return list(reversed(path))

# --------------------------------------------------------
# 演示：从 0 号节点出发求最短路径
distances, predecessors = dijkstra(graph, 0)

print("最短距离数组：", distances)
print("前驱数组：", predecessors)

print("\n从 0 到 3 的最短路径：", get_path(predecessors, 3))

# --------------------------------------------------------
# 输出示例（可能略有不同）：
# 最短距离数组： [0, 2, 5, 7]
# 前驱数组： [None, 0, 0, 2]
#
# 从 0 到 3 的最短路径： [0, 2, 3]
#
# 要点总结：
# 1) 适用于求单源最短路径，要求边权非负；
# 2) 使用优先队列可将复杂度优化为 O((V + E) log V)；
# 3) 前驱数组可恢复最短路径的路线；
# 4) 邻接表比邻接矩阵更适合稀疏图的高效实现。
# */