迪杰斯特算法介绍.docx

《迪杰斯特算法介绍.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<<