Dijkstra 算法初探
2024-08-23 02:59:04
一、Dijkstra 算法的介绍
Dijkstra 算法,又叫迪科斯彻算法(Dijkstra),算法解决的是有向图中单个源点到其他顶点的最短路径问题。举例来说,如果图中的顶点表示城市,而边上的权重表示著城市间开车行经的距离,Dijkstra 算法可以用来找到两个城市之间的最短路径。
三、Dijkstra 的算法实现
Dijkstra 算法的输入包含了一个有权重的有向图 G,以及G中的一个来源顶点 S。我们以 V 表示 G 中所有顶点的集合,以 E 表示G 中所有边的集合。
(u, v) 表示从顶点 u 到 v 有路径相连,而边的权重则由权重函数 w: E → [0, ∞] 定义。因此,w(u, v) 就是从顶点 u 到顶点 v 的非负花费值(cost),边的花费可以想像成两个顶点之间的距离。
任两点间路径的花费值,就是该路径上所有边的花费值总和。
已知有 V 中有顶点 s 及 t,Dijkstra 算法可以找到 s 到 t 的最低花费路径(例如,最短路径)。这个算法也可以在一个图中,找到从一个顶点 s 到任何其他顶点的最短路径。
符号代表:有向图:G 来源顶点:S 顶点:V 边:E 发费值:w(u, v)
Dijkstra 算法的实现一(维基百科):
注意:u := Extract_Min(Q) 在顶点集合 Q 中搜索有最小的 d[u] 值的顶点 u。这个顶点被从集合 Q 中删除并返回给用户。
1 function Dijkstra(G, w, s)
2 for each vertex v in V[G] // 初始化
3 d[v] := infinity
4 previous[v] := undefined
5 d[s] := 0
6 S := empty set
7 Q := set of all vertices
8 while Q is not an empty set // Dijkstra演算法主體
9 u := Extract_Min(Q)
10 S := S union {u}
11 for each edge (u,v) outgoing from u
12 if d[v] > d[u] + w(u,v) // 拓展边(u,v)
13 d[v] := d[u] + w(u,v)
14 previous[v] := u
如果我们只对在 s 和 t 之间寻找一条最短路径的话,我们可以在第9行添加条件如果满足 u = t 的话终止程序。现在我们可以通过迭代来回溯出 s 到 t 的最短路径:
1 s := empty sequence
2 u := t
3 while defined u
4 insert u to the beginning of S
5 u := previous[u]
现在序列 S 就是从 s 到 t 的最短路径的顶点集.
Dijkstra 算法的实现二(算法导论):
DIJKSTRA(G, w, s)
1 INITIALIZE-SINGLE-SOURCE(G, s)
2 S ← Ø
3 Q ← V[G] //V*O(1)
4 while Q ≠ Ø
5 do u ← EXTRACT-MIN(Q) //EXTRACT-MIN,V*O(V),V*O(lgV)
6 S ← S ∪{u}
7 for each vertex v ∈ Adj[u]
8 do RELAX(u, v, w) //松弛技术,E*O(1),E*O(lgV)。
因为Dijkstra算法总是在V-S中选择“最轻”或“最近”的顶点插入到集合S中,所以我们说它使用了贪心策略。 此Dijkstra 算法的最初的时间复杂度为O(V*V+E),源点可达的话,O(V*lgV+E*lgV)=>O(E*lgV)当是稀疏图的情况时,E=V*V/lgV,算法的时间复杂度可为O(V^2)。但我们知道,若是斐波那契堆实现优先队列的话,算法时间复杂度,则为O(V*lgV + E)
最新文章
- MVC采用Jquery实现局部刷新
- ABP理论学习之授权(Authorization)
- mapreduce性能提升2
- JS 职责链模式
- 基于word制作网站webhelp
- DouNet学习_Excel导入导出
- HDU 5679 Substring 后缀数组判重
- RHCS集群理论暨最佳实践
- weblogic使用脚本部署
- C++ inline和#define宏的区别
- 一起来学Go --- (go的枚举以及数据类型)
- Python——Flask框架——电子邮件
- 微信小程序获取复选框全选,反选选中的值
- 算法课笔记系列(七)—— 平摊分析Amortized Analysis
- TensorFlow 算术运算符
- 剑指offer编程题Java实现——面试题8旋转数组的最小数字
- ArcGIS Runtime SDK for iOS开发地图图层-图形图层
- swiper 视频轮番
- SSM商城项目(三)
- 关于android studio 出现Error:Execution failed for task ':app:preDebugAndroidTestBuild'. 的解决办法