Dijkstra 算法的流程图
定义全局变量
dist[N]，
vo,vi,G[N][N]
初始化变量
s[N],i,j,prev[N]
K=0
K<N
V=0
V<N
final[v] =
false;dist[v] =
cost[v0][v];
Y
final[v0] =
true
N
i=0
i<N-1
初始最短长度无
穷大
W=0
W<N
!final[w] &&
dist[w] < min
Min =
dist[w]
v = w;
Y
Y
Y
W++
加入新边
final[v] =
true
W=0
W<N
!final[w] &&
dist[v] +
cost[v][w] <
dist[w]
dist[w] =
dist[v] +
cost[v][w];
Y
W++
N
i=0
i<N-1
i<N-1
输出dist[i]v0++;
Y
N
Y
N
N
I++
N
K++;
N
I++
END
需求和规格说明：
Dijkstra 算法是典型最短路算法，用于计算一个节点到其他所有节点
的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到
终点为止。Dijkstra 算法能得出最短路径的最优解，但由于它遍历计
算的节点很多，所以效率低。
算法本身并不是按照我们的思维习惯——求解从原点到第一个点的
最短路径，再到第二个点的最短路径，直至最后求解完成到第 n 个点
的最短路径，而是求解从原点出发的各有向路径的从小到大的排列，
但是算法最终确实得到了从原点到图中其余各点的最短路径，可以说
这是个副产品，对于算法的终结条件也应该以求得了原点到图中其余
各点的最短路径为宜。清楚了算法的这种巧妙构思后，理解算法本身
就不是难题了。实现注释：
想要实现的功能：
Dijkstra 算法是用来求任意两个顶点之间的最短路径。在该实验中，
我们用邻接矩阵来存储图。在该程序中设置一个二维数组来存储任意
两个顶点之间的边的权值。用户可以将任意一个图的信息通过键盘输
入，让后在输入要查找的两个顶点，程序可以自动求出这两个顶点之
间的最短路径。
已经实现的功能：
在该实验中，我们用邻接矩阵来存储图。在该程序中设置一个全局变
量的二维数组，用它来存储任意两个顶点之间的边的权值。然后通过
最短路径的计算，输入从任意两个顶点之间的最短路径的大小。
用户手册：
对于改程序，不需要客户进行什么复杂的输入，关键是用来存放图的
任意两个顶点之间的边的权值的二维数组的初始化，即将要通过
Dijkstra 算法求最短路径的图各条边的权值放入二维数组中。这样程
序就可以自动的计算出任意两个顶点之间的最短路径并且进行输出。
设计思想：
s 为源，w[u，v] 为点 u 和 v 之间的边的长度，结果保存在 dist[]
初始化：源的距离 dist[s]设为 0，其他的点距离设为无穷大，同时把
所有的点状态设为没有扩展过。
循环 n-1 次：
1. 在没有扩展过的点中取一距离最小的点 u，并将其状态设为已扩展。
2. 对于每个与 u 相邻的点 v，如果 dist[u] + w[u，v] < dist[v]，那么
把 dist[v]更新成更短的距离 dist[u] + w[u，v]。此时到点 v 的最短路
径上，前一个节点即为 u。
结束：此时对于任意的 u，dist[u]就是 s 到 u 的距离。
程序源代码：
#include <>
#include ""
#define true 1
#define false 0
#define I 9999 // 无穷大
#define N 5 // 城市顶点的数目
int cost[N][N] = {
{0,3,I,8,I},
{3,0,5,I,4},
{I,5,0,4,7},
{8,I,4,0,2},
{I,4,7,2,0}};
int dist[N]; // 存储当前最短路径
长度
int v0 = 'A' - 65; // 初始点是 A
int main()
{
int final[N],i,v,w,min,k;
printf("\n 任意两个定点之间的最短路径如下：\n\n");
for(k=0;k<N;k++)
{
// 初始化最短路径长度数据，所有数据都不是最终数据
for (v = 0; v < N; v++)
{
final[v] = false;
dist[v] = cost[v0][v];
}
// 首先选 v0 到 v0 的距离一定最短，最终数据
final[v0] = true;
// 寻找另外 N-1 个结点
for (i = 0; i < N-1; i++)
{
min = I; // 初始最短长度无穷大
// 寻找最短的边
for (w = 0; w < N; w++)
{
if (!final[w] && dist[w] < min)
{
min = dist[w];
v = w;
}
}
final[v] = true; // 加入新边
for (w = 0; w < N; w++)
{ // 更新 dist[] 数据
if (!final[w] && dist[v] + cost[v][w] < dist[w])
{
dist[w] = dist[v] + cost[v][w];
}
}
}
for (i = 0; i < N; i++)
{
printf("%c->%c: %2d\t", v0 + 65, i + 65, dist[i]);
}
printf("\n");
v0++;
}
return 0;
}
运行结果：
调试报告：
错误：
运行结果如下：
而正确的运行结果是这样的：
出现的问题是在寻找最短路径和更新 dist[] 数据的两个 for 循环之间
少了一个赋值语句。如下：
final[v] = true; // 加入新边
当每次找到从 v0 到其它各定点的最短路径是，将该定点标记为已经
找到了最短路径，下次查找是不再对该顶点的 dist[]的值进行改变。
