最短路径问题是什么？Dijkstra算法实现

小老鼠

发布时间：2025-08-22 15:09:01

338人浏览过

来源于php中文网

原创

Dijkstra算法是解决最短路径问题的经典方法，适用于边权为正的图，通过贪心策略和优先级队列高效确定从起点到各节点的最短路径。

最短路径问题是什么？dijkstra算法实现

最短路径问题，简单来说，就是在给定网络或图中，找到从一个节点到另一个节点成本最低（或距离最短）的路径。而Dijkstra算法，正是解决这类问题的经典方法之一，它能有效地找出图中所有边权均为正数时的最短路径。它就像一个智能导航员，总能帮你找到最省钱或最省时的路线。

Dijkstra算法实现

Dijkstra算法的核心思想，其实是一种贪心策略：它总是选择当前已知最短路径的未访问节点进行扩展。听起来有点抽象？想象一下，你从家出发，想去几个朋友家拜访，每次都先去离你最近、且你还没去过的朋友家，然后看看从他家出发，能不能更近地到达其他朋友家。

具体实现上，我们需要维护几个关键信息：

距离数组 (dist[])：记录从起点到每个节点的当前最短距离。初始化时，起点为0，其他为无穷大。
访问状态 (visited[])：标记节点是否已经被“确定”了最短路径。
优先级队列 (priority_queue)：存储 (距离, 节点) 对，每次取出距离最小的节点。

算法步骤概览：

将起点加入优先级队列，距离设为0。
当队列不为空时： a. 取出队列中距离最小的节点
```
u
```
。 b. 如果
```
u
```
已经被访问过，跳过。 c. 标记
```
u
```
为已访问。 d. 遍历
```
u
```
的所有邻居
```
v
```
： i. 如果
```
u
```
到
```
v
```
的路径加上
```
u
```
的距离比当前
```
v
```
的距离更短，就更新
```
v
```
的距离，并将
```
(新距离, v)
```
加入优先级队列。

import heapq

def dijkstra(graph, start_node):
    # graph: 邻接列表表示，例如 {node: [(neighbor, weight), ...]}
    distances = {node: float('inf') for node in graph}
    distances[start_node] = 0

    priority_queue = [(0, start_node)] # (distance, node)

    # visited_nodes = set() # 也可以用这个，但通常在循环内部判断更高效

    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)

        # 如果当前距离比已记录的要大，说明我们已经找到了更短的路径，跳过
        # 这是为了处理优先级队列中可能存在的“过期”数据
        if current_distance > distances[current_node]:
            continue

        # 遍历当前节点的所有邻居
        for neighbor, weight in graph.get(current_node, []):
            distance = current_distance + weight

            # 如果通过当前节点到达邻居的路径更短
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

# 示例用法
# graph_example = {
#     'A': [('B', 1), ('C', 4)],
#     'B': [('C', 2), ('D', 5)],
#     'C': [('D', 1)],
#     'D': []
# }
# shortest_paths = dijkstra(graph_example, 'A')
# print(shortest_paths) # {'A': 0, 'B': 1, 'C': 3, 'D': 4}

为什么最短路径问题如此重要？

我个人觉得，最短路径问题的重要性几乎渗透在我们日常生活的方方面面，只是我们很少意识到。你想想看，你打开手机导航，它瞬间给你规划出几条路线，还告诉你哪条最快——这背后就是最短路径算法在飞速运转。物流公司要优化配送路线，减少油耗和时间；网络数据包要在复杂的互联网中找到最快传输路径；甚至在游戏里，NPC角色怎么找到最快路径追击玩家，或者寻路去完成任务，都离不开它。

它不仅仅是理论上的一个算法，更是支撑现代社会高效运转的基石之一。没有它，我们现在习以为常的便利，比如即时送达的外卖、流畅的网络视频通话，可能都难以实现。在我看来，理解最短路径，某种程度上就是理解现代信息流和物流的底层逻辑。

Dijkstra算法的局限性：负权边怎么办？

Dijkstra算法确实非常高效，但它有一个核心前提：图中所有的边权都必须是非负数。如果你的图中存在负权边（比如，某条路径能让你“赚”到时间或资源，表现为负值），Dijkstra就会“失效”了。为什么呢？因为Dijkstra的贪心策略是基于“一旦一个节点的最短路径被确定，它就不会再被更新”这个假设的。但如果存在负权边，一个看似已经确定最短路径的节点，未来可能会通过一条包含负权边的路径，被进一步“缩短”。