【学习】《算法图解》第九章学习笔记：迪杰斯特拉算法
一、迪杰斯特拉算法概述
迪杰斯特拉算法（Dijkstra’s algorithm）是一种解决带权有向图上单源最短路径问题的贪心算法，由荷兰计算机科学家艾兹赫尔·迪杰斯特拉（Edsger W. Dijkstra）于1956年提出。该算法常用于路由协议，也可以用作其他图算法的子程序。
（一）算法适用场景
迪杰斯特拉算法适用于：
- 带权有向图（每条边都有权重）
- 所有权重都为非负值（不能有负权边）
- 需要找出从一个顶点到图中所有其他顶点的最短路径
（二）算法基本思想
迪杰斯特拉算法的核心思想是：
- 从起点开始，逐步扩展到图中的其他顶点
- 每次选择当前未访问的距离最小的顶点
- 更新该顶点的所有邻居的距离值
- 重复这个过程，直到所有顶点都被访问过
二、算法步骤详解
（一）算法流程
- 创建两个集合：已访问顶点集合和未访问顶点集合
- 将起点的距离设为0，其他顶点的距离设为无穷大
- 重复以下步骤，直到所有顶点都被访问：
a. 从未访问顶点中选择距离最小的顶点
b. 将该顶点标记为已访问
c. 更新该顶点的所有邻居的距离
（二）图示说明
以《算法图解》中的例子为例，假设我们要找从起点到终点的最短路径：
- 起点的距离为0，其他顶点的距离为无穷大
- 访问起点的所有邻居，更新它们的距离
- 从未访问顶点中选择距离最小的顶点
- 重复步骤2和3，直到访问到终点或所有顶点都被访问
三、算法实现
（一）伪代码
function Dijkstra(Graph, source):
// 初始化
dist[source] = 0 // 源点到自身的距离为0
for each vertex v in Graph:
if v ≠ source:
dist[v] = infinity // 初始时，源点到其他顶点的距离为无穷大
previous[v] = undefined // 前驱节点初始化为undefined
Q = all vertices in Graph // 未访问顶点集合
while Q is not empty:
u = vertex in Q with min dist[u] // 选择距离最小的顶点
remove u from Q
for each neighbor v of u:
alt = dist[u] + length(u, v) // 计算经过u到达v的距离
if alt < dist[v]: // 如果找到更短的路径
dist[v] = alt // 更新距离
previous[v] = u // 更新前驱
return dist[], previous[] // 返回距离和路径（二）Python实现
def dijkstra(graph, start):
# 初始化距离字典和前驱字典
distances = {node: float('infinity') for node in graph}
distances[start] = 0
previous = {node: None for node in graph}
# 未访问节点集合
unvisited = list(graph.keys())
while unvisited:
# 找到未访问节点中距离最小的节点
current = min(unvisited, key=lambda node: distances[node])
# 如果当前节点的距离是无穷大，说明剩余未访问节点与起点不连通
if distances[current] == float('infinity'):
break
# 从未访问集合中移除当前节点
unvisited.remove(current)
# 检查当前节点的所有邻居
for neighbor, weight in graph[current].items():
distance = distances[current] + weight
# 如果找到更短的路径，更新距离和前驱
if distance < distances[neighbor]:
distances[neighbor] = distance
previous[neighbor] = current
return distances, previous
# 构建路径函数
def build_path(previous, start, end):
path = []
current = end
while current != start:
path.append(current)
current = previous[current]
# 如果没有路径到达终点
if current is None:
return None
path.append(start)
path.reverse() # 反转路径，从起点到终点
return path（三）示例应用
以《算法图解》中的例子为例：
# 图的表示（使用邻接表）
graph = {
'start': {'a': 6, 'b': 2},
'a': {'fin': 1},
'b': {'a': 3, 'fin': 5},
'fin': {}
}
# 运行算法
distances, previous = dijkstra(graph, 'start')
path = build_path(previous, 'start', 'fin')
print("最短距离:", distances['fin'])
print("最短路径:", path)输出：
最短距离: 6
最短路径: ['start', 'b', 'a', 'fin']四、算法分析
（一）时间复杂度
- 使用普通数组实现：O(V²)，其中V是顶点数
- 使用优先队列（二叉堆）实现：O((V+E)logV)，其中E是边数
- 使用斐波那契堆实现：O(E + VlogV)
（二）空间复杂度
- O(V)，需要存储距离数组和前驱数组
（三）算法优缺点
优点：
- 能够找到单源最短路径
- 算法思想简单直观
- 实现相对容易
缺点：
- 不能处理负权边
- 在稠密图上性能不如Bellman-Ford算法
- 基本实现的时间复杂度较高
五、迪杰斯特拉算法的应用
（一）实际应用场景
- 网络路由协议：如OSPF（开放最短路径优先）协议
- 地图导航系统：计算最短或最快路线
- 网络延迟优化：寻找网络中延迟最小的路径
- 机器人路径规划：规划机器人移动的最佳路径
- 社交网络分析：计算用户之间的最短关系路径
（二）算法变种和改进
- 双向迪杰斯特拉算法：同时从起点和终点开始搜索，提高效率
- A*算法：结合启发式信息，加速搜索过程
- 多级迪杰斯特拉：预处理图数据，加速查询
- 约束迪杰斯特拉：添加额外约束条件的变种
六、与其他最短路径算法的比较
（一）迪杰斯特拉 vs Bellman-Ford
| 算法 | 优点 | 缺点 | 时间复杂度 | 适用场景 |
|---|---|---|---|---|
| 迪杰斯特拉 | 速度较快 | 不能处理负权边 | O((V+E)logV) | 所有权重为非负的图 |
| Bellman-Ford | 可以处理负权边 | 速度较慢 | O(VE) | 可能存在负权边的图 |
（二）迪杰斯特拉 vs Floyd-Warshall
| 算法 | 优点 | 缺点 | 时间复杂度 | 适用场景 |
|---|---|---|---|---|
| 迪杰斯特拉 | 单源最短路径效率高 | 需要多次运行才能得到所有顶点对的最短路径 | O((V+E)logV) | 单源最短路径问题 |
| Floyd-Warshall | 一次运行可得到所有顶点对的最短路径 | 不能处理负权回路 | O(V³) | 所有顶点对的最短路径问题 |
七、常见问题与解决方案
（一）处理负权边
迪杰斯特拉算法不能处理负权边，因为一旦有负权边，贪心策略就可能失效。解决方案是使用Bellman-Ford算法。
（二）提高算法效率
- 使用优先队列（如二叉堆或斐波那契堆）实现未访问节点集合
- 在稀疏图上使用邻接表而非邻接矩阵
- 对于特定应用，可以使用双向搜索或A*算法等启发式方法
（三）处理大规模图
- 使用分层技术减少搜索空间
- 预处理图数据，构建索引
- 使用并行计算加速算法执行
八、总结
迪杰斯特拉算法是一种经典的单源最短路径算法，它通过贪心策略逐步找到从起点到图中所有其他顶点的最短路径。该算法思想简单直观，实现相对容易，但不能处理负权边。
在实际应用中，迪杰斯特拉算法被广泛应用于网络路由、地图导航、机器人路径规划等领域。通过使用优先队列等数据结构，可以有效提高算法的效率。
对于不同的应用场景，我们可能需要选择不同的最短路径算法或迪杰斯特拉算法的变种，以满足特定的需求和约束条件。
参考资料
- 《算法图解》第九章，Aditya Bhargava 著
- Introduction to Algorithms (CLRS), 第24章
- 维基百科：迪杰斯特拉算法
- Khan Academy: Dijkstra’s Shortest Path Algorithm