算法十一:Dijkstra算法 - 一个点到各个点的最短路径
Dijkstra算法是指定一个源点,求得这个源点到各个点的最短路径。Dijkstra算法通过不断的松弛边,每次更新相邻点的路径,使之两点之间的距离成为最短的路径。Dijkstra算法缺点是不能有负权边的值。
松弛边:点A到点B的距离是10,点A到点C的距离是15,点B到点C的距离是3,那么点A到点C的最短距离就是13。此时15这个值将会被废弃,永不使用,以后谈论点A到点C的距离都是直接说13。这就是松弛边。
现在有如下图,6个点,9条边,边是有方向的哦。
Dijkstra算法的步骤,假设源点为点(1):
1、先求得源点到各个点的距离。则数组为dis['1'=>0, '2'=>1, '3'=>12, '4'=>'∞', '5'=>'∞', '6'=>'∞'];并且用数组e[i][j]表示点i到点j的距离。
2、将各个点分为2个部分,P部分是已知的点1到该点距离为最短路径的点的集合,此时P部分只有点1到点1的距离为0是已知的,点1到点2,点1到点3的距离是不是最短路径暂时不可是,所以他们不属于这部分。Q部分是未知的点1到该点距离为最短路径的点的集合。
3、在集合Q中选择一个点,这个点距离源点(1)号点最近,即步骤一得出的dis数组中该key所对应的值最小,此时这个点为2号点,因为dis[2]最小,为1。则点1到点2的距离dis[2]是最短的路径,已经已知了,所以将(2)号点加入到集合P中。此时以(2)好点为源点,对所有的边松弛一次,看看有没有一个点X,可以使得点1到点2再到点X的距离小于点1到点X的距离,如果有,则点1到点X的最短路径就是点1到点2再到点X的值。即如果dis[3] > dis[2] + e[2][x],则dis[3] = dis[2] + e[2][x]。
4、重复第三步,知道集合Q为空。
Dijkstra算法的代码如下:
#include <stdio.h>
int main(){
int startPoint = 1;
int limitValue = 999;
int e[10][10], dis[10], book[10], i, j, m, n, point1, point2, length, u, v, min;
//n是点数,m是边数
scanf("%d %d", &n, &m);
//如果i=j,就是自己到自己的距离,那么就是0,否则,就初始化非正无穷
for(i=1; i<=n; i++){
for(j=1; j<=n; j++){
if(i==j)
e[i][j] = 0;
else
e[i][j] = limitValue;
}
}
//边的长度,即点到点的距离
for(i=1; i<=m; i++){
scanf("%d %d %d", &point1, &point2, &length);
e[point1][point2] = length;
}
//初始化源点到各点的距离的数组,我们的源点为1
for(i=1; i<=n; i++){
dis[i] = e[startPoint][i];
}
//book数组用来标记那个点是已经走过了的。
for(i=1; i<=n; i++){
book[i] = 0;
}
//从源点开始
book[startPoint] = 1;
//以下就是Dijkstra算法的重点,是核心思想
for(i=1; i<=n-1; i++){
//找到离远点最近的点
min = limitValue;
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++){
//如果小于limitValue,则证明点u到点v是有路走的
if(e[u][v] < limitValue){
if(dis[v] > dis[u] + e[u][v]){
dis[v] = dis[u] + e[u][v];
}
}
}
}
//输出
for(i=0; i<=n; i++){
printf("%d ", dis[i]);
}
return 0;
}
输入:
6 9
1 2 1
1 3 12
2 3 9
2 4 3
3 5 5
4 3 4
4 5 13
4 6 15
5 6 4
输出
0 1 8 4 13 17
这个输出便是点1到各个点的最短距离。
Ps:本算法参考《啊哈!算法》一书。