Dijkstra algorithm [Dijkstra最短路径算法]
前文介绍的Floyd-Warshell算法是解决多源最短路径问题[mutiple-source shortest-paths problem]，即多个起始点的最短路径，而Dijkstra最短路径算法则是解决单源最短路径问题[single-source shortest-paths problem]，也即是给定一个点，只需计算出该点到达另一点的最短路径即可。Dijkstra算法是贪心算法思想的成功应用，其核心思想是每次找到离源点最近的一个顶点，然后以该顶点为中心进行扩展，最终得到源点到其余所有点的最短路径。
首先考虑下图的路径信息，现在想要知道节点1到分别到2，3，4，5，6的最短距离。
我们依然使用一个距离矩阵来描述各个点之间的距离。
| 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|
| 1 | 0 | 1 | 12 | X | X | X |
| 2 | X | 0 | 9 | 3 | X | X |
| 3 | X | X | 0 | X | 5 | X |
| 4 | X | X | 4 | 0 | 13 | 15 |
| 5 | X | X | X | X | 0 | 4 |
| 6 | X | X | X | X | X | 0 |
除此之外，Dijkstra算法还需要维护一个一维数组来表示节点1到其他节点的距离。其初始值即为矩阵第一列，也就是最开始，节点1到达其他节点的距离。
| 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|
| 0 | 1 | 12 | X | X | X |
然后，因为是以节点1为起始，先寻找距离节点1最近的点，跟节点1相邻的点是2和3，2为最近的点。那么现在节点1到节点2的距离就从估计值变为确定值 [确定值用粗体显示]，因为我们已经从节点1开始选中最短的路径，其他任何路径包括有中转节点的情况，都不可能比这条路径更短。
| 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|
| 0 | 1 | 12 | X | X | X |
既然已经选中节点2，那么下面就开始考虑节点2，从节点2可以到达节点3和节点4。然后就需要看这两天路线的出现能否将原有的1->3和1->4变短，即比较e[1][3]和e[1][2]+e[2][3], e[1][4]和e[1][2]+e[2][4]。根据计算结果更新数组
| 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|
| 0 | 1 | 10 | 4 | X | X |
因为1->2的距离已经确定，再从3，4，5，6中选择距离1最近的距离，也就是节点4[距离为4]，则4成为一个确定值。
| 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|
| 0 | 1 | 10 | 4 | X | X |
以此类推，因为选中了4，则观察从节点4可以到达的节点有3，5，6，然后看新的路径能否缩短原路长度，也就是比较e[1][3]和e[1][4]+e[4][3]，e[1][5]和e[1][4]+e[4][5]，e[1][6]和e[1][4]+e[4][6]，然后根据结果更新数组，
| 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|
| 0 | 1 | 8 | 4 | 17 | 19 |
然后再从3，5，6中选择离1最近的点也就是3，则1->3的距离8就变为确定值。
| 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|
| 0 | 1 | 8 | 4 | 17 | 19 |
然后考虑3的相邻节点并重新计算路径更新数组，3的相邻节点只有5，所以直比较e[1][5]和e[1][3] + e[3][5]
| 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|
| 0 | 1 | 8 | 4 | 13 | 19 |
然后再次从5，6中选择离1最近的点，就是5，距离13也就成为确定值
| 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|
| 0 | 1 | 8 | 4 | 13 | 19 |
然后5可以到达的节点只有6，所以比较e[1][6]和e[1][5]+e[5][6],
| 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|
| 0 | 1 | 8 | 4 | 13 | 17 |
现在只剩下节点6，并且节点6也无法到达任意节点，所以17就成为确定值。
| 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|
| 0 | 1 | 8 | 4 | 13 | 17 |
具体步骤：
-
将所有的顶点分为两部分：已知最短路程的顶点集合P和未知最短路径的顶点集合Q。最开始，已知最短路径的顶点集合P中只有源点一个顶点。我们这里用一个book[i]数组来记录哪些点在集合P中。例如对于某个顶点i，如果boo[i]为1则表示这个顶点在集合P中，如果book[i]为0则表示这个顶点在集合Q中。
-
设置源点s到自己的最短路径为0即dis=0。若存在源点有能直接到达的顶点i，则把dis[i]设为e[s][i]。同时把所有其它[源点不能直接到达的]顶点的最短路径为设为∞。
-
在集合Q的所有顶点中选择一个离源点s最近的顶点u[即dis[u]最小]加入到集合P。并考察所有以点u为起点的边，对每一条边进行松弛操作。例如存在一条从u到v的边，那么可以通过将边u->v添加到尾部来拓展一条从s到v的路径，这条路径的长度是dis[u]+e[u][v]。如果这个值比目前已知的dis[v]的值要小，我们可以用新值来替代当前dis[v]中的值。
-
重复第3步，如果集合Q为空，算法结束。最终dis数组中的值就是源点到所有顶点的最短路径。
对应的完整代码：
#include <stdio.h>
int main()
{
int e[10][10],dis[10],book[10],i,j,n,m,t1,t2,t3,u,v,min;
int inf=99999999; //用inf(infinity的缩写)存储一个我们认为的正无穷值
//读入n和m，n表示顶点个数，m表示边的条数
scanf("%d %d",&n,&m);
//初始化
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i==j) e[i][j]=0;
else e[i][j]=inf;
//读入边
for(i=1;i<=m;i++)
{
scanf("%d %d %d",&t1,&t2,&t3);
e[t1][t2]=t3;
}
//初始化dis数组，这里是1号顶点到其余各个顶点的初始路程
for(i=1;i<=n;i++)
dis[i]=e[1][i];
//book数组初始化
for(i=1;i<=n;i++)
book[i]=0;
book[1]=1;
//Dijkstra算法核心语句
for(i=1;i<=n-1;i++)
{
//找到离1号顶点最近的顶点
min=inf;
for(j=1;j<=n;j++)
{
if(book[j]==0 && dis[j]<min)
{
min=dis[j];
u=j;
}
}
book[u]=1;
for(v=1;v<=n;v++)
{
if(e[u][v]<inf)
{
if(dis[v]>dis[u]+e[u][v])
dis[v]=dis[u]+e[u][v];
}
}
}
//输出最终的结果
for(i=1;i<=n;i++)
printf("%d ",dis[i]);
getchar();
getchar();
return 0;
}
本文部分内容源自互联网，坐在马桶上看算法。