Dijkstra算法
2024-10-01 21:51:11
发布于:浙江
Dijkstra算法是一种用于计算图中两个节点之间最短路径的经典算法,通常用于加权图(边权值非负)。它的核心思想是逐步扩展最短路径树,直到到达目标节点。下面是Dijkstra算法的详细原理和执行步骤:
算法原理
-
初始化:
- 创建一个集合
S
,用于存储已经找到最短路径的节点。 - 为每个节点设置一个初始距离值,起始节点的距离设为0,其他节点的距离设为无限大(表示不可达)。
- 创建一个优先队列(或最小堆),用于按距离值从小到大选择节点。
- 创建一个集合
-
选择节点:
- 从优先队列中取出距离值最小的节点
u
,将其加入集合S
。
- 从优先队列中取出距离值最小的节点
-
更新距离:
- 对于每个与
u
直接相连的邻接节点v
,计算从起始节点到v
的新距离d(u) + w(u, v)
(w(u, v)
是边u
到v
的权重)。 - 如果这个新距离小于当前存储在
dist[v]
中的距离值,则更新dist[v]
。
- 对于每个与
-
重复:
- 重复步骤2和步骤3,直到所有节点都被加入集合
S
,或直到优先队列为空。
- 重复步骤2和步骤3,直到所有节点都被加入集合
-
输出结果:
- 最终,
dist
数组中的值就是从起始节点到每个节点的最短路径长度。
- 最终,
执行步骤示例
假设有以下加权图:
1
A-------B
| /|
4| 2 |3
| / |
C-------D
5
-
图的表示:可以用邻接矩阵或邻接表表示图。这里用邻接矩阵表示:
A B C D A 0 1 4 ∞ B 1 0 2 3 C 4 2 0 5 D ∞ 3 5 0
-
初始化:
- 设置
dist[A] = 0
,dist[B] = ∞
,dist[C] = ∞
,dist[D] = ∞
。 - 集合
S = {}
。
- 设置
-
选择节点:
- 从优先队列中取出
A
(最小距离为0),加入集合S
,更新邻接节点的距离:dist[B] = min(∞, 0 + 1) = 1
dist[C] = min(∞, 0 + 4) = 4
- 现在
dist = {A: 0, B: 1, C: 4, D: ∞}
。
- 从优先队列中取出
-
重复步骤:
-
选择
B
(距离为1),加入集合S
,更新邻接节点的距离:dist[C] = min(4, 1 + 2) = 3
dist[D] = min(∞, 1 + 3) = 4
-
现在
dist = {A: 0, B: 1, C: 3, D: 4}
。 -
选择
C
(距离为3),加入集合S
,但没有更新,因为没有比3更短的路径。 -
选择
D
(距离为4),加入集合S
,同样没有更新。
-
-
结束:
- 最终结果为
dist = {A: 0, B: 1, C: 3, D: 4}
,即从A
到各节点的最短路径长度。
- 最终结果为
复杂度分析
- 时间复杂度:使用优先队列(如最小堆),Dijkstra算法的时间复杂度为
O((V + E) log V)
,其中V
是顶点数量,E
是边的数量。 - 空间复杂度:主要消耗在存储距离值和优先队列上,空间复杂度为
O(V)
。
注意事项
- Dijkstra算法仅适用于非负权重的图。如果图中存在负权边,应该使用Bellman-Ford算法。
希望以上内容能帮助你理解Dijkstra算法的原理和执行步骤!如果还有其他问题,欢迎提问!
这里空空如也
有帮助,赞一个