二之再续、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算法,需要理解图的表示方法、优先队列的概念以及如何有效地更新路径信息。以下是关于这个主题的详细讲解。 首先,图在C语言中通常使用邻接矩阵或邻接表来表示。邻接矩阵是一个二维数组,其...
在这个项目中,"标准C的图的实现+BFS和DFS遍历+Dijkstra算法+Prim算法+Kruskal算法实现"涵盖了图的多种核心操作和算法。接下来,我们将详细讨论这些知识点。 首先,我们来看图的实现。在标准C语言中,图可以使用...
二叉堆、二项堆和斐波那契堆是数据结构中的重要概念,它们都是堆数据结构的不同变体,主要用于高效地实现某些特定操作,如查找最大或最小元素、优先队列以及各种排序算法。在C++编程语言中,理解和实现这些堆结构...
二(再续)、Dijkstra 算法+fibonacci 堆的逐步c 实现 二(三续)、Dijkstra 算法+Heap 堆的完整c 实现源码 三、dynamic programming 四、BFS 和DFS 优先搜索算法 五、红黑树算法的实现与剖析 五(续)、教你透彻...
dijkstra算法的三种实现:数组,二叉堆,斐波那契堆 + 部分实验报告 dijkstra算法的三种实现:数组,二叉堆,斐波那契堆 + 部分实验报告 dijkstra算法的三种实现:数组,二叉堆,斐波那契堆 + 部分实验报告
经典算法,让你沉醉其中无法自拔。 一、A*搜索算法 一(续)、A*,Dijkstra,BFS 算法...二(再续)、Dijkstra 算法+fibonacci 堆的逐步 c 实现 二(三续)、Dijkstra 算法+Heap 堆的完整 c 实现源码 三、动态规划算法
斐波那契堆是一种高效的优先队列数据结构,它在计算机科学中,特别是在算法和图论领域具有重要的应用。在《算法导论》一书中,斐波那契堆被广泛讨论,因为它在解决诸如最短路径、最小生成树等算法问题时能提供高效的...
Balavenkatesh Bathrinarayanan采用斐波那契堆实现Dijkstra算法,这表明他在优化算法执行速度方面有所考虑。通常,简单的优先队列如二叉堆在Dijkstra算法中的表现不如斐波那契堆,因为二叉堆在删除最小元素和合并...
二(再续)、Dijkstra 算法+fibonacci堆的逐步c实现 二(三续)、Dijkstra 算法+Heap堆的完整c实现源码 三、动态规划算法 四、BFS和DFS优先搜索算法 五、教你透彻了解红黑树 (红黑数系列六篇文章之其中两篇) 五...
### Dijkstra(迪杰斯特拉)算法概述 Dijkstra算法是一种经典的单源最短路径算法,主要用于计算...在实际应用中,Dijkstra算法可以根据不同的需求进行优化,例如通过使用斐波那契堆等高效数据结构进一步提高算法性能。
Dijkstra算法可以使用多种数据结构实现,包括数组、链表以及优先队列(如二叉堆、 Fibonacci堆等)。优先队列可以高效地找到距离最小的节点,从而优化算法的性能。 **4. 应用场景:** - 路径规划:在地图导航系统中...
迪杰斯特拉(Dijkstra)算法是一种用于寻找图中两点之间最短路径的著名算法,由荷兰计算机科学家艾兹格·...此外,对于优化,可以考虑使用二叉堆或者 Fibonacci heap 来提高优先队列的效率,尤其是在处理大规模图时。
Dijkstra算法,由荷兰...Dijkstra算法是图论中基础且重要的算法之一,理解并掌握其原理和实现对于解决实际问题具有重要意义。通过阅读提供的代码,你可以更深入地了解算法的实现细节,以及如何在具体场景中应用它。
2. Fibonacci堆优化:在处理大规模图时,Dijkstra算法的时间复杂度可以通过使用Fibonacci堆等高效数据结构来优化,提高效率。 3. 实际应用:Dijkstra算法广泛应用于路由器的路由选择、道路网络的最短路径规划、社交...
本篇文章将探讨三种不同类型的堆:二叉堆(Binary Heap)、斐波那契堆(Fibonacci Heap)和配对堆(Pairing Heap),以及它们在Dijkstra算法中的效率差异。 **二叉堆**是最基础的堆结构,分为最大堆和最小堆。最大...
Dijkstra算法的基本思想是使用贪心策略,逐步扩展最短路径树。算法的核心在于维护一个优先队列(通常用最小堆实现),存储未确定最短路径的节点,并不断更新节点的最短距离。初始化时,源节点距离为0,其他所有节点...
在这个C语言实现的版本中,我们将深入探讨斐波那契堆的核心概念、结构以及其操作。 斐波那契堆主要由几个部分组成:单链表和双链表。每个节点包含一个键值、一个指向前驱的指针、一个指向后继的指针,以及一个子...
Dijkstra算法是一种经典的图论算法,用于解决单源最短路径问题,即从图中的一个顶点(起点)到其他所有顶点的最短路径。在这个实现中,它使用邻接表作为图的存储结构,这比邻接矩阵更节省空间,特别是对于稀疏图(边...