单源最短路径的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
//-------------------------------------数据声明------------------------------------------------ //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[v] = 0; s[v] = true;
for (int i = 1; i < n; i++)
dist[i] = c[v][i]; s[i] = false;
//初始都未用过该点
if (dist[i] == MAX) else
prev[i] = v; prev[i] = 0;
//表示v到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保存当前邻接点中距离最小
的点的号码
for (int j = 1; j <= n; j++)
}
temp = dist[j];
s[u] = true; k++; b[k] = u;
cout << \ << endl; cout << \迭代次数：\ << i << endl; cout << \顶点为：\; cout << v << \; for (int i = 1; i <= k; i++)
cout << b[i] << \;
cout << endl;
//
}
if ((!s[j]) && c[u][j] < MAX) { }
int newdist = dist[u] + c[u][j]; if (newdist < dist[j]) { }
dist[j] = newdist; prev[j] = u;
//更新dist //记录前驱顶点
cout << \单源路径分别为：\ << 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++) //
t[i] = prev[i];
int p[LEN];
for (int i = 2; i <= n; i++) {
cout << \ << i << \ << dist[i] << \ \;
}
}
cout << \路径为：\ << v << \; /*while (t[i] != v) { }*/
int m = prev[i]; int k=0; while (m != v) { }
for (int x = k; x >= 1; x--)
k++; p[k] = m; m = prev[m]; cout << t[i] << \ t[i] = prev[t[i]];
cout << p[x] << \;
cout << i; cout << endl;
int main()