编辑“︁Dijkstra算法”︁

{{DISPLAYTITLE:Dijkstra算法}}

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

== 算法概述 ==

Dijkstra算法的核心思想是'''贪心策略'''，通过逐步扩展已知的最短路径集合来求解问题。算法维护两个集合：
* '''已确定最短路径的顶点集合'''（通常记为$S$）
* '''未确定最短路径的顶点集合'''（通常记为$Q$）

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

== 算法实现 ==

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

<syntaxhighlight lang="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
</syntaxhighlight>

=== 输入输出示例 ===

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

<syntaxhighlight lang="python">
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}
}
</syntaxhighlight>

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

<syntaxhighlight lang="python">
print(dijkstra(graph, 'A'))
</syntaxhighlight>

输出结果：
<syntaxhighlight lang="python">
{'A': 0, 'B': 1, 'C': 3, 'D': 4}
</syntaxhighlight>

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

== 算法可视化 ==

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

<mermaid>
graph LR
    A((A)) --1--> B((B))
    A --4--> C((C))
    B --2--> C
    B --5--> D((D))
    C --1--> D
</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. '''物流配送'''：优化配送路线以减少运输成本

=== 城市导航示例 ===

考虑一个简化城市道路网：
* 节点代表交叉口
* 边代表道路，权重代表行驶时间（分钟）

<mermaid>
graph LR
    Home --5--> A
    Home --10--> B
    A --3--> C
    B --2--> C
    C --7--> Work
    A --8--> Work
    B --4--> Work
</mermaid>

使用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算法不仅有助于解决实际问题，也是培养算法思维的重要一步。

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:图论算法]]