迪杰斯特算法介绍.docx

迪杰斯特算法介绍.docx

ID:57645407

大小:54.34 KB

页数:6页

时间:2020-08-30

迪杰斯特算法介绍.docx_第1页
迪杰斯特算法介绍.docx_第2页
迪杰斯特算法介绍.docx_第3页
迪杰斯特算法介绍.docx_第4页
迪杰斯特算法介绍.docx_第5页
资源描述:

《迪杰斯特算法介绍.docx》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、Dijkstar算法算法简介  Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等。Dijkstra一般的表述通常有两种方式,一种用永久和临时标号方式,一种是用OPEN,CLOSE表的方式,这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权回路。算法描述  (这里描述的是从节点1开始到各点的dijkstra算法,其中Wa-

2、>b表示a->b的边的权值,d(i)即为最短路径值)  1.置集合S={2,3,...n},数组d(1)=0,d(i)=W1->i(1,i之间存在边)or+无穷大(1.i之间不存在边)  2.在S中,令d(j)=min{d(i),i属于S},令S=S-{j},若S为空集则算法结束,否则转3  3.对全部i属于S,如果存在边j->i,那么置d(i)=min{d(i),d(j)+Wj->i},转2复杂度分析  Dijkstra算法的时间复杂度为O(n^2)  空间复杂度取决于存储方式,邻接矩阵为O(n^2) 问题描述:给定图G,求其顶点t到其他所有点的最短路径。

3、算法描述:将图所有点的集合S分为两部分,V和S-V。V集合是已经得到最短路径的点的集合,在初始情况下V中只有一个顶点t,S-V是还未得到最短路径点的集合。然后,在每一次迭代过程中取得S-V集中到V集合任一点距离最短的点,将其加到V集合,从V-S集合删除。重复此过程直到S-V集合为空。时间复杂度:示例:伪代码:算法实现输入输出格式      输入格式:  第1行:一个数n,代表有n个节点  第2-n+1行:每行n个数,代表图的邻接矩阵,没有边相连为-1  输出格式:  第1行:n-1个数,分别是1号节点到2-n号节点的最短路径算法证明使用数学归纳法,假设在某次

4、迭代(不是第一次迭代)之前,S中的点的权值都是最短路径,我们证明某次迭代之后从Q中取出的点的权值依然是这个点的最短路径。利用反正,假设本次迭代从Q中取出的点u的权值不是最短的,那么存在一条从v到u的路径小于这个权值。可知这条路径上u的前趋一定有一个属于S(因为至少v是属于S的),假设属于S的第一个前趋为x,而这条路径上x的后继为y。由算法的性质可知,这条路径从v到y的权值一定是不小于从Q中取出的u的权值的,那么可知刚刚找到的这条从v到u的路径权值也不小于从Q中取出的u的权值。这与假设矛盾。故u的权值是最短的。而算法第一次迭代也满足从Q中取出的店的权值为最优这

5、个性质,故算法的正确性得证。C++代码实现#include#includeconstintmaxdist=9999;usingnamespacestd;/*n是总的结点数,v是出发结点,dist是距离,pre前一个结点,d是结点间的权值*/voidDijkstra(intn,intv,vector&dist,vector&pre,vector>&d){vectors(n+1);for(inti=1;i<=n;i++){dist[i]=d[v][i];if(dist[i

6、]

7、+d[best][j];if(newdistpre,intinit,intfina){inttemp=fina;vectort;while(temp!=init){t.push_back(temp);temp=pre[fina];fina=temp;}cout<";for(inti=t.size();i>1;i--){cout<";}cout<

8、);}intmain(){intn,l;cout<<

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。