单源最短路径的dijkstra算法.doc

-
. z.
单源最短路径的Dijkstra算法：
问题描述：
给定一个带权有向图G=〔V，E〕，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。
-
. z.
单源最短路径的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就记录了从源到所有其他顶点之间的最短路径长度。
源代码：
*include<iostream>
*defineMA* 1000
*defineLEN 100
intk=0, b[LEN];
usingnamespacestd;
//-------------------------------------数据声明------------------------------------------------
//c[i][j]表示边 (i,j)的权
//dist[i]表示当前从源到顶点i的最短特殊路径长度
//prev[i]记录从源到顶点i的最短路径上的i的前一个顶点
//---------------------------------------------------------------------------------------------
voidDijkstra(intn, intv, intdist[], intprev[], intc[][LEN])
{
bools[LEN]; // 判断是否已存入该点到S集合中
for (inti = 1; i <= n; i++)
{
dist[i] = c[v][i];
s[i] = false; //初始都未用过该点
if (dist[i] == MA*)
prev[i] = 0; //表示v到i前一顶点不存在
else
prev[i] = v;
}
dist[v] = 0;
-
. z.
s[v] = true;
for (inti = 1; i < n; i++)
{
inttemp = MA*;
intu = v;
for (intj = 1; j <= n; j++)
if ((!s[j]) && (dist[j] < temp)) //j不在s中，v到j距离不在为无