二之再续、Dijkstra 算法+fibonacci堆的逐步c实现
作者:JULY、二零一一年三月十八日
出处:http://blog.csdn.net/v_JULY_v
----------------------------------
引言:
来考虑一个问题,
平面上6个点,A,B,C,D,E,F,假定已知其中一些点之间的距离,
现在,要求A到其它5个点,B,C,D,E,F各点的最短距离。
如下图所示:
经过上图,我们可以轻而易举的得到A->B,C,D,E,F各点的最短距离:
目的 路径 最短距离
A=>A, A->A 0
A=>B, A->C->B 3+2=5
A=>C, A->C 3
A=>D, A->C->D 3+3=6
A=>E, A->C->E 3+4=7
A=>F, A->C->D->F 3+3+3=9
我想,如果是单单出上述一道填空题,要你答出A->B,C,D,E,F各点的最短距离,
一个小学生,掰掰手指,也能在几分钟之内,填写出来。
我们的问题,当然不是这么简单,上述只是一个具体化的例子而已。
实际上,很多的问题,如求图的最短路径问题,就要用到上述方法,不断比较、不断寻找,以期找到最短距离的路径,此类问题,便是Dijkstra 算法的应用了。当然,还有BFS算法,以及更高效的A*搜寻算法。
A*搜寻算法已在本BLOG内有所详细的介绍,本文咱们结合fibonacci堆实现Dijkstra 算法。
即,Dijkstra + fibonacci堆 c实现。
我想了下,把一个算法研究够透彻之后,还要编写代码去实现它,才叫真正掌握了一个算法。本BLOG内经典算法研究系列,已经写了18篇文章,十一个算法,所以,还有10多个算法,待我去实现。
代码风格
实现一个算法,首先要了解此算法的原理,了解此算法的原理之后,便是写代码实现。
在打开编译器之前,我先到网上搜索了一下“Dijkstra 算法+fibonacci堆实现”。
发现:网上竟没有过 Dijkstra + fibonacci堆实现的c代码,而且如果是以下几类的代码,我是直接跳过不看的:
1、没有注释(看不懂)。
2、没有排版(不舒服)。
3、冗余繁杂(看着烦躁)。
fibonacci堆实现Dijkstra 算法
ok,闲话少说,咱们切入正题。下面,咱们来一步一步利用fibonacci堆实现Dijkstra 算法吧。
前面说了,要实现一个算法,首先得明确其算法原理及思想,而要理解一个算法的原理,又得知道发明此算法的目的是什么,即,此算法是用来干什么的?
由前面的例子,我们可以总结出:Dijkstra 算法是为了解决一个点到其它点最短距离的问题。
我们总是要找源点到各个目标点的最短距离,在寻路过程中,如果新发现了一个新的点,发现当源点到达前一个目的点路径通过新发现的点时,路径可以缩短,那么我们就必须及时更新此最短距离。
ok,举个例子:如我们最初找到一条路径,A->B,这条路径的最短距离为6,后来找到了C点,发现若A->C->B点路径时,A->B的最短距离为5,小于之前找到的最短距离6,所以,便得此更新A到B的最短距离:为5,最短路径为A->C->B.
好的,明白了此算法是干什么的,那么咱们先用伪代码尝试写一下吧(有的人可能会说,不是吧,我现在,什么都还没搞懂,就要我写代码了。额,你手头不是有资料么,如果全部所有的工作,都要自己来做的话,那就是一个浩大的工程了。:D。)。
咱们先从算法导论上,找来Dijkstra 算法的伪代码如下:
DIJKSTRA(G, w, s)
1 INITIALIZE-SINGLE-SOURCE(G, s) //1、初始化结点工作
2 S ← Ø
3 Q ← V[G] //2、插入结点操作
4 while Q ≠ Ø
5 do u ← EXTRACT-MIN(Q) //3、从最小队列中,抽取最小点工作
6 S ← S ∪{u}
7 for each vertex v ∈ Adj[u]
8 do RELAX(u, v, w) //4、松弛操作。
伪代码毕竟与能在机子上编译运行的代码,还有很多工作要做。
首先,咱们看一下上述伪代码,可以看出,基本上,此Dijkstra 算法主要分为以下四个步骤:
1、初始化结点工作
2、插入结点操作
3、从最小队列中,抽取最小点工作
4、松弛操作。
ok,由于第2个操作涉及到斐波那契堆,比较复杂一点,咱们先来具体分析第1、2、4个操作:
1、得用O(V)的时间,来对最短路径的估计,和对前驱进行初始化工作。
INITIALIZE-SINGLE-SOURCE(G, s)
1 for each vertex v ∈ V[G]
2 do d[v] ← ∞
3 π[v] ← NIL //O(V)
4 d[s] 0
我们根据上述伪代码,不难写出以下的代码:
void init_single_source(Graph *G,int s)
{
for (int i=0;i<G->n;i++) {
d[i]=INF;
pre[i]=-1;
}
d[s]=0;
}
2、插入结点到队列的操作
2 S ← Ø
3 Q ← V[G] //2、插入结点操作
代码:
for (i=0;i<G->n;i++)
S[i]=0;
4、松弛操作。
首先得理解什么是松弛操作:
Dijkstra 算法使用了松弛技术,对每个顶点v<-V,都设置一个属性d[v],用来描述从源点s到v的最短路径上权值的上界,称为最短路径的估计。
RELAX(u, v, w)
1 if d[v] > d[u] + w(u, v)
2 then d[v] ← d[u] + w(u, v)
3 π[v] ← u //O(E)
同样,我们不难写出下述代码:
void relax(int u,int v,Graph *G)
{
if (d[v]>d[u]+G->w[u][v])
{
d[v] = d[u]+G->w[u][v]; //更新此最短距离
pre[v]=u; //u为v的父结点
}
}
再解释一下上述relax的代码,其中u为v的父母结点,当发现其父结点d[u]加上经过路径的距离G->w[u][v],小于子结点到源点的距离d[v],便得更新此最短距离。
请注意,说的明白点:就是本来最初A到B的路径为A->B,现在发现,当A经过C到达B时,此路径距离比A->B更短,当然,便得更新此A到B的最短路径了,即是:A->C->B,C 即成为了B的父结点(如此解释,我相信您已经明朗。:D。)。
即A=>B <== A->C->B,执行赋值操作。
ok,第1、2、4个操作步骤,咱们都已经写代码实现了,那么,接下来,咱们来编写第3个操作的代码:3、从最小队列中,抽取最小点工作。
相信,你已经看出来了,我们需要构造一个最小优先队列,那用什么来构造最小优先队列列?对了,堆。什么堆最好,效率最高,呵呵,就是本文要实现的fibonacci堆。
为什么?ok,请看最小优先队列的三种实现方法比较:
EXTRACT-MIN + RELAX
I、 简单方式: O(V*V + E*1)
II、 二叉/项堆: O(V*lgV + |E|*lgV)
源点可达:O(E*lgV)
稀疏图时,有E=o(V^2/lgV),
=> O(V^2)
III、斐波那契堆:O(V*lgV + E)
其中,V为顶点,E为边。好的,这样我们就知道了:Dijkstra 算法中,当用斐波纳契堆作优先队列时,算法时间复杂度为O(V*lgV + E)。
额,那么接下来,咱们要做的是什么列?当然是要实现一个fibonacci堆了。可要怎么实现它,才能用到我们
Dijkstra 算法中列?对了,写成一个库的形式。库?呵呵,是一个类。
ok,以下就是这个fibonacci堆的实现:
由于本BLOG日后会具体阐述这个斐波那契堆的各项操作,限于篇幅,在此,就不再啰嗦解释上述程序了。
ok,实现了fibonacci堆,接下来,咱们可以写Dijkstra 算法的代码了。为了版述清晰,再一次贴一下此算法的伪代码:
DIJKSTRA(G, w, s)
1 INITIALIZE-SINGLE-SOURCE(G, s)
2 S ← Ø
3 Q ← V[G] //第3行,INSERT操作,O(1)
4 while Q ≠ Ø
5 do u ← EXTRACT-MIN(Q) //第5行,EXTRACT-MIN操作,V*lgV
6 S ← S ∪{u}
7 for each vertex v ∈ Adj[u]
8 do RELAX(u, v, w) //第8行,RELAX操作,E*O(1)
编写的Dijkstra算法的c代码如下:
更好的代码,还在进一步修正中。日后,等完善好后,再发布整个工程出来。
下面是演示此Dijkstra算法的工程的俩张图(0为源点,4为目标点,第二幅图中的红色路径即为所求的0->4的最短距离的路径):
完。
版权所有。转载本BLOG内任何文章,请以超链接形式注明出处。谢谢,各位。
分享到:
相关推荐
二叉堆(最小堆)+二项堆+斐波那契堆 根基算法导论C++实现
二(再续)、Dijkstra 算法+fibonacci 堆的逐步c 实现 二(三续)、Dijkstra 算法+Heap 堆的完整c 实现源码 三、dynamic programming 四、BFS 和DFS 优先搜索算法 五、红黑树算法的实现与剖析 五(续)、教你透彻...
dijkstra算法的三种实现:数组,二叉堆,斐波那契堆 + 部分实验报告 dijkstra算法的三种实现:数组,二叉堆,斐波那契堆 + 部分实验报告 dijkstra算法的三种实现:数组,二叉堆,斐波那契堆 + 部分实验报告
经典算法,让你沉醉其中无法自拔。 一、A*搜索算法 一(续)、A*,Dijkstra,BFS 算法...二(再续)、Dijkstra 算法+fibonacci 堆的逐步 c 实现 二(三续)、Dijkstra 算法+Heap 堆的完整 c 实现源码 三、动态规划算法
二(再续)、Dijkstra 算法+fibonacci堆的逐步c实现 二(三续)、Dijkstra 算法+Heap堆的完整c实现源码 三、动态规划算法 四、BFS和DFS优先搜索算法 五、教你透彻了解红黑树 (红黑数系列六篇文章之其中两篇) 五...
作者使用C#和C++实现斐波那契堆
迪克斯特拉斯 Balavenkatesh Bathrinarayanan使用斐波那契堆来实现Dijkstra的算法。 使用Binary Trie实现路由算法。
本人参照《算法导论》实现的斐波那契堆的源代码,用C语言实现。
第1部分:Dijkstra使用斐波那契堆的单源最短路径算法: •实现了Dijkstra的“单源最短路径”算法,以查找和打印无向图中任意两个给定节点之间的最短路径 •通过使用斐波那契堆来存储该图,优化了算法的运行时...
摊还分析11.1 一个无关的智力问题11.2 二项队列11.3 斜堆11.4 斐波那契堆11.4.1 切除左式堆中的节点11.4.2 二项队列的懒惰合并11.4.3 斐波那契堆操作11.4.4 时间界的证明11.5 伸展树总结练习参考文献第12章 高级数据...
我在这个实验中的目标是展示不同实现的强度,并调查现有开源斐波那契堆实现的性能。 所有的理论知识都可以在 24.3 和 19 中找到。 为了更深入地了解测量,我决定将文本分成 4 部分: 与此 GitHub 存储库并行,我在...
图算法:图算法用于处理图结构的数据,如最短路径算法(如Dijkstra算法、Floyd-Warshall算法)、最小生成树算法(如Prim算法、Kruskal算法)等。 动态规划:动态规划是一种通过将问题分解成更小的子问题来解决复杂...
摊还分析11.1 一个无关的智力问题11.2 二项队列11.3 斜堆11.4 斐波那契堆11.4.1 切除左式堆中的节点11.4.2 二项队列的懒惰合并11.4.3 斐波那契堆操作11.4.4 时间界的证明11.5 伸展树小结练习参考文献第12章 高级...
这个斐波那契堆实现是在 MATLAB 中开发的,用于一般用途,但其特定目的是稍后与“Matlog”使用的 Dijkstra 算法实现集成。 有关更多详细信息,请参阅 README.pdf 文件。 要创建一个名为 myHeap 的堆,应该执行以下 ...
基于Python实现的数据结构与算法完整源代码+超详细注释(包含46个作业项目) ...42_最短距离Dijkstra算法和最小生成树prim算法的区别 a1_查找第一个和最后一个元素位置 a2_斐波那契数列 aa_LCS aa_最长公共子序列
9.3.2 Dijkstra算法 9.3.3 具有负边值的图 9.3.4 无圈图 9.3.5 所有点对最短路径 9.3.6 最短路径的例子 9.4 网络流问题 9.5 最小生成树 9.5.1 Prim算法 9.5.2 Kruskal算法 9.6 深度优先搜索的应用 9.6.1 无向图 ...
ADS_Project 使用斐波那契堆的高级数据结构 Dijkstra 算法
9.3.2 Dijkstra算法 9.3.3 具有负边值的图 9.3.4 无环图 9.3.5 所有顶点对的最短路径 9.3.6 最短路径举例 9.4 网络流问题 9.5 最小生成树 9.5.1 Prim算法 9.5.2 Kruskal...
24.3 Dijkstra算法 24.4 差分约束和最短路径 24.5 最短路径性质的证明 思考题 本章注记 第25章 所有结点对的最短路径问题 25.1 最短路径和矩阵乘法 25.2 Floyd?Warshall算法 25.3 用于稀疏图...