一、Dijkstra算法的贪心本质

很多人日常选路线的时候，都会不自觉用类似Dijkstra的思路：比如从家去公司，面前有三条分叉路，分别是2分钟、5分钟、3分钟的，你肯定先选2分钟的那条，因为当前看来它是最近的，到了之后再看从这个节点出发的新路线，继续选最近的——这就是贪心算法的核心：每次选当前状态下最优的选项，希望最终得到全局最优解。Dijkstra算法就是把这种生活化的选路逻辑，用到了带权重的图结构里，解决“两个点之间最短路径”的问题。我们用Python实现来直观感受这个过程，示例代码如下：

# Dijkstra算法Python实现，技术栈：Python 3.x
import heapq

def dijkstra(graph, start):
    # 初始化：distance存每个节点到起点的最短距离，初始除起点为0外，其余设为无穷大（代表暂时不可达）
    distance = {node: float('inf') for node in graph}
    distance[start] = 0
    # 优先队列（小顶堆）：存储(当前距离, 节点)，会自动按距离从小到大排序，每次取出最小距离的节点
    priority_queue = []
    heapq.heappush(priority_queue, (0, start))
    # visited集合：标记已确定最短路径的节点，避免重复处理（后续不会有更短路径）
    visited = set()

    while priority_queue:
        current_dist, current_node = heapq.heappop(priority_queue)
        # 若节点已处理过，直接跳过（之前已经找到过更短的路径）
        if current_node in visited:
            continue
        # 标记为已处理，此时该节点到起点的最短距离已确定
        visited.add(current_node)
        # 遍历当前节点的所有邻居，更新邻居的距离
        for neighbor, weight in graph[current_node].items():
            # 只有邻居未处理，且经过当前节点的路径更短时，才更新距离
            if neighbor not in visited and current_dist + weight < distance[neighbor]:
                distance[neighbor] = current_dist + weight
                # 更新后将新的距离和节点推入优先队列，等待后续处理
                heapq.heappush(priority_queue, (distance[neighbor], neighbor))
    return distance

# 示例图：用邻接表存储带权重的图，键是节点，值是该节点的邻居及对应边权重
sample_graph = {
    'A': {'B': 2, 'C': 5},
    'B': {'A': 2, 'C': 3, 'D': 1},
    'C': {'A': 5, 'B': 3, 'D': 2},
    'D': {'B': 1, 'C': 2}
}

# 计算从节点A出发到所有节点的最短路径
result = dijkstra(sample_graph, 'A')
print("从A出发到各节点的最短距离：", result)

运行后输出的结果是{'A':0, 'B':2, 'C':5, 'D':3}，完全符合我们预期的最短路径：A到B直接走2分钟，A到D走A→B→D（2+1=3分钟），A到C走A→B→C（2+3=5分钟），这就是贪心逻辑在实际问题中的落地。

二、最短路径计算的核心逻辑

刚才的示例其实已经把核心逻辑拆解得很清楚，再用通俗的话再梳理一遍：

2.1 图的存储选邻接表

邻接表就像每个人的通讯录，只存和自己直接相连的人，比邻接矩阵（像全班同学名单，不管是否认识都列出来）更节省空间，尤其适合道路、网络这种稀疏图（大部分节点之间没有直接连接），刚才的示例就是典型的邻接表写法。

2.2 距离初始化的关键意义

把起点距离设为0，其他节点设为无穷大，相当于一开始“只知道自己在起点，其他地方都远得不可想象”，后续每找到一条更短的路径，就把对应节点的距离更新，这个初始化是算法正确运行的基础，不能错。

2.3 贪心的核心：优先队列

优先队列的作用就是每次取出“当前最近的未处理节点”，不会在更远的路径上浪费时间，同时因为算法的前提是所有边的权重都是非负的（没有倒贴钱或者时间倒流的情况），所以第一次处理某个节点时，得到的一定是它的最短路径，不会出现后续有更短路径的情况，这也是为什么能使用贪心逻辑的核心前提。

三、常见误区拆解

Dijkstra算法看起来简单，但实际用的时候很容易踩坑，最常见的几个误区：

3.1 误区一：给带负权重的图用

这是最致命的误区，因为Dijkstra的前提是边权重非负，如果出现负权重，算法会直接失效。比如把刚才示例里B到C的权重改成-3，再运行原来的代码，就会得到错误结果。我们用代码演示这个反例：

# 带负权重的错误示例图
bad_graph = {
    'A': {'B': 2, 'C':5},
    'B': {'A':2, 'C':-3, 'D':1},
    'C': {'A':5, 'B':-3, 'D':2},
    'D': {'B':1, 'C':2}
}
# 错误调用Dijkstra算法
error_result = dijkstra(bad_graph, 'A')
print("错误结果：", error_result)

运行后输出的A到C的距离是5，但实际正确路径是A→B→C，距离是2+(-3)=-1，算法之所以错，是因为处理B节点时，C已经被标记过（之前从A到C是5），所以B到C的-1不会被更新，这就是负权重导致的问题，这种场景下要换Bellman-Ford算法才行。

3.2 误区二：乱用已处理标记

有人会忘记加visited集合，或者提前标记节点，这都会导致结果错误或者效率变低。比如去掉代码里的visited判断，虽然非负权的图最终结果还是对的，但会重复处理节点，效率下降，而如果是负权图，可能会出现死循环或者完全错误的结果，所以必须正确标记已处理的节点。

3.3 误区三：初始化距离错误

比如把起点的距离设成无穷大，或者把其他节点的距离设成0，这样结果会完全乱套，比如把distance初始化为所有都是0，那A到B的距离会变成0，完全不符合实际，所以初始化必须严格按照要求：起点为0，其他为无穷大。

四、应用场景

Dijkstra算法因为效率高、逻辑清晰，被广泛用在各种需要最短路径的场景里：

4.1 地图导航

高德、百度地图的路线规划核心就是Dijkstra或者它的优化版A*算法，因为道路的权重（距离、时间、费用）都是非负的，符合算法前提，能快速计算出最优路线，比如避开拥堵、选择距离最短的路线，都是基于这个逻辑。

4.2 网络路由

互联网里的OSPF协议（内部网关协议），就是用Dijkstra算法计算路由器之间的最短路径，确保数据能以最快的速度从源节点传到目标节点，不会绕远路。

4.3 物流配送

外卖配送、快递的路线规划，比如要给多个用户配送，用Dijkstra计算每个节点的最短距离，再结合动态规划找到最优的配送顺序，减少配送时间，提高效率。

五、技术优缺点

5.1 优点

  • 效率高：用优先队列实现的Dijkstra算法，时间复杂度是O((V+E)logV)，比暴力枚举的O(V²)快很多，适合处理中等规模以上的图，比Bellman-Ford（O(VE)）快一个数量级以上。
  • 逻辑简单：符合人的直觉，容易理解，代码实现也不复杂，是学习图算法的基础，很多更复杂的路径算法都是在它的基础上优化的。

5.2 缺点

  • 局限性大：只能处理边权重非负的图，遇到负权或者负权环就会失效，这是它最主要的缺陷，比如金融里的汇率兑换可能有权重为负的情况，就不能用。
  • 贪心的局限性：贪心逻辑是每次选当前最优，虽然大部分场景正确，但如果前提不成立，就会出问题，这也是很多人踩坑的原因。

六、注意事项

6.1 必须先检查边权重

使用Dijkstra之前，一定要确保所有边的权重都是≥0的，哪怕有一个负边，结果都会出错，这是最关键的前提，不能省略检查步骤。

6.2 优先队列的使用

优先队列要选小顶堆，因为需要每次取出距离最小的节点，Python的heapq默认是小顶堆，没问题，其他语言比如Java的PriorityQueue默认是大顶堆，需要反转排序规则，否则结果会完全错误。

6.3 节点标记的正确性

必须正确使用visited集合，不要提前标记，也不要遗漏标记，确保只有已确定最短路径的节点才会被标记，避免重复处理和错误更新。

6.4 图存储的选择

稀疏图（大部分节点没有连接）用邻接表，密集图（几乎所有节点都有连接）用邻接矩阵，邻接矩阵的查询速度更快，适合特殊场景，要根据实际情况选择。