Dijkstra 最短路径

"""Dijkstra 最短路径 —— 站内原创示例代码

用途：给定带权无向图，求两个节点之间的最短路径。
适用：路径规划、图论作业、导航算法入门。
依赖：仅 Python 标准库（heapq）。
运行：python dijkstra-path.py
许可：MIT（开源拾遗原创，可自由使用与修改）
"""

import heapq


def dijkstra(graph, start):
    """返回 (最短距离表, 前驱表)。graph 形如 {节点: [(邻居, 权重), ...]}。"""
    dist = {node: float("inf") for node in graph}
    prev = {node: None for node in graph}
    dist[start] = 0
    visited = set()
    queue = [(0, start)]

    while queue:
        d, u = heapq.heappop(queue)
        if u in visited:
            continue
        visited.add(u)
        for v, weight in graph[u]:
            candidate = d + weight
            if candidate < dist[v]:
                dist[v] = candidate
                prev[v] = u
                heapq.heappush(queue, (candidate, v))

    return dist, prev


def shortest_path(graph, start, end):
    """返回 (路径列表, 总长度)；不可达时返回 (None, inf)。"""
    dist, prev = dijkstra(graph, start)
    if dist.get(end, float("inf")) == float("inf"):
        return None, float("inf")

    path = []
    cur = end
    while cur is not None:
        path.append(cur)
        cur = prev[cur]
    return path[::-1], dist[end]


if __name__ == "__main__":
    # 一张小地图：节点是地点，边是距离
    graph = {
        "A": [("B", 4), ("C", 2)],
        "B": [("A", 4), ("C", 1), ("D", 5)],
        "C": [("A", 2), ("B", 1), ("D", 8), ("E", 10)],
        "D": [("B", 5), ("C", 8), ("E", 2)],
        "E": [("C", 10), ("D", 2)],
    }

    path, total = shortest_path(graph, "A", "E")
    print("最短路径:", " -> ".join(path))
    print("总长度:", total)

    # 自检：结果应为 A -> C -> B -> D -> E，长度 10
    assert path == ["A", "C", "B", "D", "E"], path
    assert total == 10, total
    print("断言通过")