迪杰特斯拉算法的代码实现

左手的ㄟ右手 2022-06-12 09:51 276阅读 0赞

1，迪杰斯特拉算法介绍  
迪杰斯特拉算法是典型最短路径算法，用于计算图或网中某个特定顶点到其他所有顶点的最短路径。主要特点是以起始点为中心向外，层层扩展，直到扩展覆盖所有顶点。  
2，迪杰斯特拉算法思想  
设G=(V,E)为一个带全有向图，把图中顶点集合V分成两组。第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将所到达最短路径的顶点加入到集合S中，直到全部顶点都加入到S中）。第二组为其余未确定最短路径的顶点集合（用U表示，U=V-S，U中的顶点不断的加入到S中，直到U为空，S=V）。在U加入S的过程中，始终保持源点到S中各顶点的最短路径长度小于或等于源点到U中任意顶点的最短路径长度。  
3，迪杰斯特拉算法执行步骤  
设 n 为图 G=(V,E) 中的顶点数，dist\[n\] 存放从源点到每个终点当前最短路径的长度，path\[n\] 存放相应路径，S 为已求得最短路径的终点的集合，U为V-S,初始为不含有源点的所有顶点。  
（1）初始化已求的最短路径的集合S为只含有元素源点a，S=｛a｝。  
（2）从U中选取一个距离源点v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。  
（3）以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u（u U）的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值为顶点k的距离加上顶点k到u边上的权。

（4）重复步骤（2）和（3）直到所有顶点都包含在S中。

![Center][]

C++ Code

<table style="width:100%; font-family:'Consolas','Courier New'; font-size:12px; vertical-align:text-top; line-height:15px"> 
 <tbody> 
 <tr> 
 <td style="color:#008284; background-color:#e3e3e3; vertical-align:text-top"> 
 <div style="margin:7px; text-align:right; white-space:nowrap">
 1 
 2 
 3 
 4 
 5 
 6 
 7 
 8 
 9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 
 22 
 23 
 24 
 25 
 26 
 27 
 28 
 29 
 30 
 31 
 32 
 33 
 34 
 35 
 36 
 37 
 38 
 39 
 40 
 41 
 42 
 43 
 44 
 45 
 46 
 47 
 48 
 49 
 50 
 51 
 52 
 53 
 54 
 55 
 56 
 57 
 58 
 59 
 60 
 61 
 62 
 63 
 64 
 65 
 66 
 67 
 
 </div> </td> 
 <td style="background-color:#008284; padding:1px"> 
 <div style="border:1px #008284 solid"></div> </td> 
 <td style="width:100%; vertical-align:text-top; background-color:rgb(239,239,239)"> 
 <div style="margin:7px"> 
 #include&lt;bits/stdc++.h&gt; 
 
 using&nbsp; 
 namespace&nbsp;std; 
 
 
 const&nbsp; 
 int&nbsp;maxnum= 
 100; 
 ///最大的节点数 
 const&nbsp; 
 int&nbsp;maxint= 
 9999;&nbsp;&nbsp; 
 ///如果两点没有路径，则设置为此较大的值 
 int&nbsp;dist[maxnum];&nbsp;&nbsp; 
 ///存储原点到各点的最短距离 
 int&nbsp;c[maxnum][maxnum];&nbsp;&nbsp; 
 ///存储图的邻接矩阵 
 int&nbsp;n,line;&nbsp;&nbsp; 
 ///节点数，和路径数 
 
 void&nbsp;dijikstr( 
 int&nbsp;n, 
 int&nbsp;v, 
 int&nbsp;dist[maxnum], 
 int&nbsp;c[maxnum][maxnum]) 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 bool&nbsp;s[maxnum];&nbsp;&nbsp; 
 ///标记这个点是否已求出最短的路径。 &nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;i= 
 1;i&lt;=n;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 ///初始化dist[]和s[] &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dist[i]=c[v][i]; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;s[i]= 
 0; 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 ///原点 &nbsp;&nbsp;&nbsp;&nbsp;s[v]= 
 1; 
 &nbsp;&nbsp;&nbsp;&nbsp;dist[v]= 
 0; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 ///原点不用再进行计算，所以从2开始 &nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;i= 
 2;i&lt;=n;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;temp=maxint; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;u=v; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;j= 
 1;j&lt;=n;j++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if((!s[j])&amp;&amp;dist[j]&lt;temp) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 ///找出剩余的&nbsp;最短路径 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;u=j; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;temp=dist[j]; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;s[u]= 
 1; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 ///更新剩余的点与原点的距离（dist） &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;j= 
 1;j&lt;=n;j++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(!s[j]&amp;&amp;c[u][j]&lt;maxint) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;newdist=dist[u]+c[u][j]; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(dist[j]&gt;newdist) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dist[j]=newdist; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 } 
 
 int&nbsp;main() 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%d&nbsp;%d",&amp;n,&amp;line); 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;i= 
 1;i&lt;=n;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;j= 
 1;j&lt;=n;j++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;c[i][j]=maxint; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;p,q,x; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;i= 
 1;i&lt;=line;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;scanf( 
 "%d&nbsp;%d&nbsp;%d",&amp;p,&amp;q,&amp;x); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if(x&lt;c[p][q]) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;c[q][p]=x; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;c[p][q]=x; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;i= 
 1;i&lt;=n;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dist[i]=maxnum; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;dijikstr(n, 
 1,dist,c); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;printf( 
 "源点到最后一个顶点的最短路径长度:%d\n",dist[n]); 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp; 
 0; 
 } 
 
 </div> </td> 
 </tr> 
 </tbody> 
</table>

测试数据：

5  
7  
1 2 10  
1 4 30  
1 5 100  
2 3 50  
3 5 10  
4 3 20  
4 5 60

结果：

[Center]: /images/20220612/9b06991b3ef7429a84584cdf83ad2808.png