单源最短路径的Dijkstra算法.docx

单源最短路径的Dijkstra 算法:
问题描述：
给定一个带权有向图G=(V, E),其中每条边的权是非负实数。另外，还给 定V中的一个顶点，称为源。现在要计算从源到所有其他各顶点的最短路长度。 这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。
算法描述：
Dijkstra 算法是解单源最短路径的一个贪心算法。基本思想是：设置顶点集
合S并不断地做贪心选择来扩充这个集合。一个顶点属于S当且仅当从源到该顶 点的最短路径长度已知。初始时，S中仅含有源。设u是G的某一个顶点，把从 源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记 录当前每个顶点所对应的最短特殊路径长度。 Dijkstra 算法每次从V-S中取出
具有最短特殊路长度的顶点u,将u添加到S中，同时对数组dist做必要的修 改。一旦S包含了所有V中顶点，dist就记录了从源到所有其他顶点之间的最 短路径长度。
源代码：
#in elude <iostream>
#defi ne MAX1000
#defi ne LEN1OO
int k=0, b[ LEN;
using namespace
std;
//
数据声明
〃c[i][j]
表示边(i,j) 的权
〃dist[i]
表示当前从源到顶点i的最短特殊路径长度
〃prev[i]
记录从源到顶点i
的最短路径上的i的前一个顶点
//
void
Dijkstra (int n, int v, int dist [], int prev [], int c[][ LEN)
{
bool s[LEN;
//
判断是否已存入该点到
S集合中
for (int i = 1
;i <=
n; i ++)
{
dist [i ]=
c[v][ i
];
s[i] = false ; //初始都未用过该点
if ( dist [i] == MAX
prev [ i ] = 0;
//表示v到i前一顶点不存在
else
prev [ i ] = v;
}
dist [ v] = 0;
s[ v] = true ;
for ( int
i = 1;
i < n; i ++)
{
int
temp =
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 ];
}
s[ u] = true ;
k++;
b[ k] = u;
cout << " " << endl;
cout << "迭代次数："<< i << endl ;
cout << "顶点为：";
cout << V << "\t";
for ( int
i = 1
;i <= k;
i ++)
cout
<< b[i ] <<