第三节 单源最短路径Dijkstra算法

  最短路径的问题在生活中是十分常见的。不仅仅是表面上的路程计算，网络中的数据传输什么的都能用到最短路径算法。我们在求最短路问题时，常用两种算法。Dijkstra单源最短路径算法和全源最短路径Floyd算法。首先对Dijkstra算法进行学习。

  Dijkstra算法用于计算一个点到其他所有节点的最短路径，是比较有代表性的最短路径算法。数学的很多学科中，都会接触到。它的思路是：把所有的顶点分为两组，一组是已经知道最短路径的，然后从未知最短路径并与之相邻的顶点中选出一个最短的放进已知组里，直到将所有的点放入已知组，找到最短路。

  举个例子，以下图为例，求A到F的最短路。

  首先，已知点是A，然后我们去找和他相邻的，距离最短的点。这时我们看到C点距离A点是3，比B的6要短，所以我们将C点放入已知集合；然后看A、C相邻的点，最短的路径是C到B，所以把B点放入已知集合。就这样一直做下去，直到将所有点放入已知点集合为止。我们将上面的过程，记录在表格里。

步骤 已知点集 B C D E F
1 A 6 3 00 00 00
2 A、C 5 6 7 00
3 A、C、B 6 7 00
4 A、C、B、D 7 9
5 A、C、B、D、E 9

  通过上面的步骤，我们将A到F的最短路找到了：A-C-D-F。除此之外，A到所有点的最短路我们都能够找到。那么，下面我们考虑用程序来实现这个过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#define INF 0x0f0f0f0f //用INF来代替正无穷（+OO）
#define N 1100
int low[N];  //low[i]数组存放A号节点到已知集合中i号节点的最短距离
int vis[N];  //vis[i] = 1表示i号节点已经在已知集合中，否则反之
int cost[N][N],n;//cost[i][j]表示i节点到j节点的直接距离
void Dijkstra(int start){
    int edge,k;
    for(int i = 1;i<=n;i++){//这里是要初始化low[]数组和vis[]数组
	low[i] = cost[start][i];
	vis[i] = 0;
    }
    vis[start] = 1;
    low[start] = 0;
    for(int i = 1;i<=n-1;i++){
	edge = INF;//edge是已知集合到未知集合的最短边
        for(int j = 1;j<=n;j++){//这里是要找到一条最短边:编号k,边长edge
	    if(vis[j]==0&&edge>low[j]){
		edge = low[j];
		k = j;
	    } 
	}
	vis[k] = 1;
	for(int j = 1;j<=n;j++){//更新得到的新节点k号节点发出去的边
	    if(vis[j]==0&&low[j] > low[k] + cost[k][j]){
		low[j] = low[k] + cost[k][j];
	    }
	}
    }
}

  上面是Dijkstra算法的C语言实现，大家可以将其作为模板记录下来，以后可以直接使用。我们就以上图为例，练习一下Dijkstra算法的使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include<stdio.h>
#include<iostream>
#include<cstring>
using namespace std;
#define INF 0x0f0f0f0f
#define N 1100
int low[N];
int vis[N];
int cost[N][N],n;
void Dijkstra(int start){
    int edge,k;
    for(int i = 1;i<=n;i++){
	low[i] = cost[start][i];
	vis[i] = 0;
    }
    vis[start] = 1;
    low[start] = 0;
    for(int i = 1;i<=n-1;i++){
	edge = INF;
        for(int j = 1;j<=n;j++){
	    if(vis[j]==0&&edge>low[j]){
		edge = low[j];
		k = j;
	    }
	}
	vis[k] = 1;
	for(int j = 1;j<=n;j++){
	    if(vis[j]==0&&low[j] > low[k] + cost[k][j]){
		low[j] = low[k] + cost[k][j];
	    }
	}
    }
}
int main() {
    memset(cost,INF,sizeof(cost));
    n=6;
    cost[1][2]=6,cost[1][3]=3;
    cost[2][3]=2,cost[2][4]=5;
    cost[3][4]=3,cost[3][5]=4;
    cost[4][5]=2,cost[4][6]=3;
    cost[5][6]=5;
    Dijkstra(1);
    printf("%d\n",low[n]);
    return 0;
}