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

单源最短路径的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>
#define MAX 1000
#define LEN 100
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 << "---------------------