《单源最短路径的Dijkstra算法.docx》由会员分享，可在线阅读，更多相关《单源最短路径的Dijkstra算法.docx（9页珍藏版）》请在三一文库上搜索。
1、.单源最短路径的Dijkstra 算法：问题描述 ：给定一个带权有向图G= （V，E），其中每条边的权是非负实数。另外，还给定 V 中的一个顶点 ，称为源 。现在要计算从源到所有其他各顶点的最短路长度。 这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。算法描述 ：Dijkstra 算法是解单源最短路径的一个贪心算法。基本思想是 ：设置顶点集合S并不断地做贪心选择来扩充这个集合。一个顶点属于 S当且仅当从源到该顶点的最短路径长度已知 。初始时 ， S中仅含有源 。设 u 是 G 的某一个顶点 ，把从源到 u 且中间只经过 S 中顶点的路称为从源到u 的特殊路径 ，并用数组 di
2、st 记录当前每个顶点所对应的最短特殊路径长度。Dijkstra 算法每次从 V-S 中取出具有最短特殊路长度的顶点u，将 u 添加到 S 中，同时对数组 dist 做必要的修改 。一旦 S 包含了所有 V 中顶点， dist 就记录了从源到所有其他顶点之间的最短路径长度。源代码 ：#include<iostream>#defineMAX 1000#defineLEN 100int k=0, b LEN;.下载可编辑 .using namespacestd ;/-数据声明 -/ci j 表示边 (i,j)的权/disti 表示当前从源到顶点i 的最短特殊路径长度/previ 记录从
3、源到顶点i 的最短路径上的i 的前一个顶点/-void Dijkstra (int n, int v, int dist , int prev , int c LEN)bool sLEN;/判断是否已存入该点到S 集合中for (int i = 1;i <=n; i+)dist i =c vi;si =false;/ 初始都未用过该点if ( dist i =MAX )prev i = 0;/ 表示 v 到 i 前一顶点不存在elseprev i = v;dist v = 0;sv =true ;.下载可编辑 .for (int i = 1;i < n; i+)int temp =
4、 MAX ;int u = v;for (int j = 1; j <=n; j+)if (! s j) && (dist j < temp )/j 不在 s 中，v 到 j 距离不在为无穷大u = j;/ u 保存当前邻接点中距离最小的点的号码temp = dist j ;su =true ;k+;bk = u;cout <<"-"<<endl ;cout <<"迭代次数 ： " <<i <<endl ;cout <<"顶点为 ： "
5、cout <<v <<"t"for (int i = 1; i <=k; i+)cout << b i <<"t"cout <<endl ;.下载可编辑 .for (int j = 1; j <=n; j+)if (! s j) &&cu j < MAX )int newdist = dist u + cu j;if ( newdist < dist j)dist j = newdist ;/ 更新 distprev j = u;/ 记录前驱顶点cout
6、<<"单源路径分别为 ：" << endl ;for (int i = 2; i <=n; i+)if (dist i !=MAX )cout <<dist i << ""cout <<endl ;cout <<"-"<<endl ;/ for (int i = 1; i <= n; i+)/ ti = previ; int pLEN;for (int i = 2;i <=n; i+).下载可编辑 .cout <<&quo
7、t;dist"<<i <<"="<<dist i << ""cout <<"路径为 ： " <<v <<"t"/*while (ti != v)cout << ti << "t"ti = prevti;*/int m = prev i;int k=0;while (m != v)k+;pk = m ;m = prevm;for (int x = k ; x >= 1;x-)
8、cout << p x << "t"cout <<i;cout <<endl ;.下载可编辑 .int main ()int i, j,k , m,n, v=1;int dist LEN, prev LEN, c LENLEN;cout <<"请输入顶点个数 :" << endl ;cin >>n ;cout <<"请输入边的个数 :" << endl ;cin >>m ;for (i = 1; i <=n ;
9、 i+)for ( j = 1;j <=n; j+)if (i =j)ci j = 0;elseci j = MAX ;cout <<"请输入每条边的权_格式为 ： i j 权 " <<endl ;for (k = 1;k <=m; k+)cin >> i;cin >> j;cin >> ci j;.下载可编辑 .Dijkstra (n , v, dist , prev, c);cout <<"-"<<endl ;system ("pause" );return 0;实验结果 ：.下载可编辑 .下载可编辑 .下载可编辑 .