图的最短路径算法之迪杰斯特拉算法
编辑时间:2017-08-19 赞：0 踩：0
导言：
本篇博客将会讲解图的最短路径求解算法中的迪杰斯特拉算法，及其C语言实现。
正文：
迪杰斯特拉算法（英语：Dijkstra's algorithm）是由荷兰计算机科学家艾兹赫尔·戴克斯特拉提出。迪科斯特拉算法是一种用于计算带权有向图中单源最短路径（SSSP：Single-Source Shortest Path）的算法，而另一种常用的最短路径求解算法弗洛伊德算法则是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法。该算法常用于路由算法或者作为其他图算法的一个子模块。在网图和非网图中，最短路径的含义是不同的。网图是两顶点经过的边上权值之和最少的路径。非网图是两顶点之间经过的边数最少的路径。举例来说，如果图中的顶点表示城市，而边上的权重表示城市间开车行经的距离，该算法可以用来找到两个城市之间的最短路径。
这个算法是通过为每个顶点 v 保留目前为止所找到的从s到v的最短路径来工作的。初始时，原点 s 的路径权重被赋为 0 （d[s] = 0）。若对于顶点 s 存在能直接到达的边（s,m），则把d[m]设为w（s, m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大，即表示我们不知道任何通向这些顶点的路径（对于所有顶点的集合 V 中的任意顶点 v， 若 v 不为 s 和上述 m 之一， d[v] = ∞）。当算法结束时，d[v] 中存储的便是从 s 到 v 的最短路径，或者如果路径不存在的话是无穷大。
边的拓展是Dijkstra 算法的基础操作：如果存在一条从 u 到 v 的边，那么从 s 到 v 的最短路径可以通过将边（u, v）添加到尾部来拓展一条从 s 到 v 的路径。这条路径的长度是 d[u] + w(u, v)。如果这个值比目前已知的 d[v] 的值要小，我们可以用新值来替代当前 d[v] 中的值。拓展边的操作一直运行到所有的 d[v] 都代表从 s 到 v 的最短路径的长度值。此算法的组织令 d[u] 达到其最终值时，每条边（u, v）都只被拓展一次。（以上两段均摘自中文维基百科）
由以上描述可知，每一条新的最短路径的求解都是通过已知的最短路径实现的，由起始点出发，一层一层地向外扩展，直至求解出起始点至终点的最短路径。因此，不难看出，迪杰斯特拉算法充分地提现了贪心的算法思想。这样讲解，大家对迪杰斯特拉算法的认识或许还是很模糊。下面我将会用图文结合的方式讲解迪杰斯特拉算法的一个例子。
图解迪杰斯特拉算法
图①
图①为原始的数据图，以求解从A点（起始点）到G点（终点）的最短路径为例。pathWeight数组存放着A点至每个定点的最短路径的权值。pathWeight[m]存放着A点至m点的最短路径。
图②
如图②所示，从起始点A开始，遍历A点至每个顶点的最短路径，其中由于A点至B、D点可达，pathWeight[B]和pathWeight[D]的值更新为5和7，而其它顶点不可达的因此其对应的pathWeight值为无穷大。
图③
如图③所示，由于已知B、D两点的最短路径，其中AD的权值最低，因此，需要以D点为中继点，寻找A点至其他顶点的最短路径。由于5+5<∞，因此，A点到E点的最短路径更新为20，即pathWeight[E]为20。同理，5+6<∞，A点至F点的最短路径更新为11，即pathWeight[F]为11。由于4+9>7，因此A、B两点间的最短路径不更新。
图④
如图④所示，在已知的最短路径以及未被作为中继点的顶点中，AB的权值最低。因此，需要以B为中继点，寻找A点至其他顶点的最短路径。由于7+8<∞，因此，A点到C点的最短路径更新为15，即pathWeight[C]为15。同理，7+7<20，因此，A点到E点的最短路径更新为14，即pathWeight[E]为14。由于7+9>5，因此A、D两点间的最短路径不更新。
图⑤
如图⑤所示，在已知的最短路径以及未被作为中继点的顶点中，A至F的权值最低。因此，需要以F为中继点，寻找A点至其他顶点的最短路径。由于11+11<∞，因此，A点到G点的最短路径更新为22，即pathWeight[G]为15。由于11+8>14，因此A、E两点间的最短路径不更新。
图⑥
如图⑥所示，在已知的最短路径以及未被作为中继点的顶点中，A至C的权值最低。因此，需要以C为中继点，寻找A点至其他顶点的最短路径。由于15+5>14，因此，A点到E点的最短路径不更新。
图⑦
如图⑦所示，在已知最短路径以及未被作为中继点的顶点中，A至E的权值最低。因此，需要以E为中继点，寻找A点至其他顶点的最短路径。由于14+9>22，因此，A点到G点的最短路径不更新。同时，由于G点是未被遍历的最后一个点，因此，G点无需再作为A点至其他顶点的中继点。至此，整个迪杰斯特拉算法的运算结束。
通过上述运算，pathWeight数组存放了起始点A至各个顶点的最短路径。因此，迪杰斯特拉算法是一种单源最短路径求解算法。
通过图文结合的方式，相信大家对迪杰斯特拉算法已经有初步的了解。下面，我将给大家呈现迪杰斯特拉算法的C语言实现。
迪杰斯特拉算法C语言实现
#include <stdio.h>
#define INFINITY 65535
#define VERTEXT_NUMBER 9
typedef struct graph{
int vertexNum;//顶点的数量
int adjList[VERTEXT_NUMBER][VERTEXT_NUMBER];//邻接表
}Graph;
//route数组存放的是在最短路径中该节点的前驱节点
//返回值为起始点verStart到终点verEnd之间最短路径的权值
int Dijktra(Graph dstGraph,int verStart,int verEnd,int *pathWeight,int *route){
int i,j,min,tmpVer;
int visited[dstGraph.vertexNum];
//给pathWeight数组赋初值
for(i = 0; i < dstGraph.vertexNum ;i++ ){
pathWeight[i] = dstGraph.adjList[verStart][i];
visited[i] = 0;
if( INFINITY != dstGraph.adjList[verStart][i]){
route[i] = verStart;
}else{
route[i] = INFINITY;
}
}
pathWeight[verStart] = 0;
route[verStart] = verStart;
visited[verStart] = 1;
//每一个循环扩展一个节点
for( i = 0 ; i < dstGraph.vertexNum ; i++ ){
min = INFINITY;
for( j = 0 ; j < dstGraph.vertexNum ; j++ ){
//从还没有走过的点中选取最近的点
if( 0 == visited[j] && pathWeight[j] < min ){
min = pathWeight[j];
tmpVer = j;
}
}
visited[tmpVer] = 1;
//更新最短路径，如果起始点从已知的路径经过最新加入的点到达该点的权值比从原来的路径到达该点的权值还要小时，更新到达该点的最短路径
for( j = 0; j < dstGraph.vertexNum ; j++ ){
if( 0 == visited[j] && (pathWeight[tmpVer] + dstGraph.adjList[tmpVer][j]) < pathWeight[j] ){
route[j] = tmpVer;
pathWeight[j] = (pathWeight[tmpVer] + dstGraph.adjList[tmpVer][j]);
}
}
}
return pathWeight[verEnd];
}
int main(void){
int table[VERTEXT_NUMBER][VERTEXT_NUMBER] = {
{0,1,5,INFINITY,INFINITY,INFINITY,INFINITY,INFINITY,INFINITY},
{1,0,3,7,5,INFINITY,INFINITY,INFINITY,INFINITY},
{5,3,0,INFINITY,1,7,INFINITY,INFINITY,INFINITY},
{INFINITY,7,INFINITY,0,2,INFINITY,3,INFINITY,INFINITY},
{INFINITY,5,1,2,0,3,6,9,INFINITY},
{INFINITY,INFINITY,7,INFINITY,3,0,INFINITY,5,INFINITY},
{INFINITY,INFINITY,INFINITY,3,6,INFINITY,0,2,7},
{INFINITY,INFINITY,INFINITY,INFINITY,9,5,2,0,4},
{INFINITY,INFINITY,INFINITY,INFINITY,INFINITY,INFINITY,7,4,0}
};
Graph mygraph;
// pathWeight数组存放着A点至每个定点的最短路径的权值,pathWeight[m]存放着A点至m点的最短路径
int pathWeight[VERTEXT_NUMBER],route[VERTEXT_NUMBER],sv;
mygraph.vertexNum = 9;
for(int i = 0;i<VERTEXT_NUMBER;i++){
for(int j = 0 ;j<VERTEXT_NUMBER;j++){
mygraph.adjList[i][j] = table[i][j];
}
}
sv = Dijktra(mygraph,0,8,pathWeight,route);
printf("sv:%d\n",sv);
for( int i=0; i<9;i++){
printf(" %d ",route[i]);
}
printf("\n");
for( int i=0; i<9;i++){
printf(" %d ",pathWeight[i]);
}
printf("\n");
return 0;
}
至此，迪杰斯特拉算法的讲解已经结束了。若是想巩固迪杰斯特拉算法的知识，可以去完成POJ的第3268题。在我的GitHub上也有该题的题解，我会在参考资料中放上链接，方便大家练习。
参考资料：
迪杰斯特拉算法中文维基：
https://zh.wikipedia.org/wiki/%E6%88%B4%E5%85%8B%E6%96%AF%E7%89%B9%E6%8B%89%E7%AE%97%E6%B3%95
关于迪杰斯特拉算法的博客
http://www.cnblogs.com/gaochundong/p/dijkstra_algorithm.html
POJ3268题题目地址：
http://poj.org/problem?id=3268