Dijkstra算法

Dijkstra算法（迪杰斯特拉算法）是一种用于求解加权图中单源最短路径问题的经典算法，由荷兰计算机科学家艾兹赫尔·戴克斯特拉于1956年提出。该算法适用于边权非负的有向图或无向图，能够高效地找到从起点到所有其他顶点的最短路径。

算法概述[编辑 | 编辑源代码]

Dijkstra算法的核心思想是贪心策略，通过逐步扩展已知的最短路径集合来求解问题。算法维护两个集合：

已确定最短路径的顶点集合（通常记为$S$）
未确定最短路径的顶点集合（通常记为$Q$）

算法步骤如下： 1. 初始化：将起点的最短距离设为0，其他顶点设为无穷大 2. 从$Q$中选出当前距离起点最近的顶点$u$，加入$S$ 3. 对$u$的所有邻居$v$进行松弛操作：如果通过$u$到$v$的路径比已知路径更短，则更新$v$的最短距离 4. 重复步骤2-3，直到$Q$为空

算法实现[编辑 | 编辑源代码]

以下是Dijkstra算法的Python实现示例，使用优先队列（最小堆）来高效地获取当前距离最近的顶点：

import heapq

def dijkstra(graph, start):
    # 初始化距离字典，所有顶点距离设为无穷大
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0  # 起点到自身的距离为0
    
    # 使用优先队列（最小堆），存储(距离, 顶点)对
    priority_queue = [(0, start)]
    
    while priority_queue:
        current_distance, current_vertex = heapq.heappop(priority_queue)
        
        # 如果当前距离大于已记录的距离，跳过
        if current_distance > distances[current_vertex]:
            continue
            
        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight
            
            # 如果找到更短的路径，则更新
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
    
    return distances

输入输出示例[编辑 | 编辑源代码]

考虑以下加权图（使用邻接表表示）：

graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}

以'A'为起点运行算法：

print(dijkstra(graph, 'A'))

输出结果：

{'A': 0, 'B': 1, 'C': 3, 'D': 4}

解释：

A→A：0（起点自身）
A→B：直接路径权重1
A→B→C：总权重1+2=3
A→B→C→D：总权重1+2+1=4

算法可视化[编辑 | 编辑源代码]

使用mermaid展示上述示例图的执行过程：

算法执行步骤： 1. 初始：S={A(0)}, Q={B(∞), C(∞), D(∞)} 2. 处理A：更新B(1), C(4) 3. 选择B(1)加入S：更新C(3), D(6) 4. 选择C(3)加入S：更新D(4) 5. 最后选择D(4)加入S

时间复杂度分析[编辑 | 编辑源代码]

Dijkstra算法的时间复杂度取决于使用的数据结构：

使用数组实现：$O(|V|^2)$，适合稠密图
使用二叉堆优先队列：$O((|E|+|V|)\log|V|)$，适合稀疏图
使用斐波那契堆：$O(|E|+|V|\log|V|)$，理论最优

其中：

$|V|$是顶点数量
$|E|$是边数量

实际应用案例[编辑 | 编辑源代码]

Dijkstra算法在现实世界中有广泛的应用： 1. 交通导航系统：计算两地之间的最短行车路线 2. 网络路由：数据包在网络中的最优传输路径 3. 社交网络：寻找人与人之间的最短联系路径 4. 物流配送：优化配送路线以减少运输成本

城市导航示例[编辑 | 编辑源代码]

考虑一个简化城市道路网：

节点代表交叉口
边代表道路，权重代表行驶时间（分钟）

使用Dijkstra算法可以找到从Home到Work的最快路径： 1. Home→A→C→Work：5+3+7=15分钟 2. Home→B→Work：10+4=14分钟（最优） 3. Home→A→Work：5+8=13分钟（假设A→Work道路因施工关闭）

算法局限性[编辑 | 编辑源代码]

Dijkstra算法有以下限制： 1. 不能处理负权边：如果图中存在负权边，算法可能得到错误结果 2. 单源最短路径：每次只能计算从一个起点出发的最短路径 3. 不适合极大图：当图非常大时，内存可能无法容纳所有数据

对于包含负权边的图，应考虑使用Bellman-Ford算法。

数学原理[编辑 | 编辑源代码]

Dijkstra算法的正确性基于以下数学原理：

最优子结构：最短路径的任何子路径也是最短路径
贪心选择性质：局部最优选择能导致全局最优解

算法证明通常使用数学归纳法： 1. 基础情况：起点到自身距离为0，正确 2. 归纳假设：前k次迭代选择的顶点最短距离正确 3. 归纳步骤：第k+1次选择的顶点u，其距离不可能通过其他未处理顶点变得更短

变体与优化[编辑 | 编辑源代码]

1. 双向Dijkstra：从起点和终点同时搜索，在中途相遇 2. A*算法：结合启发式函数，优化搜索方向 3. 层级Dijkstra：用于处理大规模图的层次化方法

练习题目[编辑 | 编辑源代码]

为巩固理解，建议尝试以下练习： 1. 手动计算给定小图中的最短路径 2. 实现算法并验证结果 3. 修改算法记录最短路径而不仅是距离 4. 处理有向图和无向图的不同情况

总结[编辑 | 编辑源代码]

Dijkstra算法是图论中最基础且重要的算法之一，它：

高效解决非负权图的单源最短路径问题
应用广泛，从导航系统到网络优化
是学习更复杂算法（如A*、Floyd-Warshall）的基础

理解Dijkstra算法不仅有助于解决实际问题，也是培养算法思维的重要一步。