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:本算法参考《啊哈!算法》一书。
友情提示:垃圾评论一律封号...