编程实现路由算法--迪杰斯特拉算法

路由算法有很多,本篇采用迪杰斯特拉最短路径法实现简单的路由算法。可能很多人一看到这个就会想到数据结构了,想到数据结构中必须要建立图的结构就很头疼,今天这种写法可以先不采用数据结构书上的写法,也可以实现相同的功能,毕竟,咱们的重点是要学习使用迪杰斯特拉算法,而不是构建图结构。

首先先来说一下迪杰斯特拉算法,从大概念上来说,该方法属于一种贪心算法,即当加进一个点后,算其相邻所有点的最短路径。详细过程如下:

如下图,要计算其中 点1 到其余各点的最短路径

image

总的计算过程见下表

image

表中红颜色代表当前行未加入到点集中的最小值,蓝颜色代表和上一个新加入点集中的点相邻的点,可能这样说还不是很清楚,就看下面的具体过程了。

第一步:初始化,把和 点1 相连的所有点的D(i)初始化,从图中可以看出,1和2、4、5相连,所以D(2)=10,D(4)=30,D(5)=100,点1和点3不直接相连,所以D(3)=65535,代表无穷大(在java里,可以用Integer.MAX_VALUE来表示无穷大)。由于现在点集中只有点1,所以找出刚才步骤1那行中D(i)最小的点,为点2(图中红色标明),将其加入到点集中。

第二步:此时点集中新加入了点2,则以点2为出发点,从图中看到只有点3与其相连,所以这一步中只需要更新D(3)即可,D(3)= min{D(3), D(2)+ d(2,3)},即D(3)= min{65535, 10+ 50} = 60,更新D(3)=60,其余点不变。这行更新完毕,发现未加入到点集中的D(4)最小,所以将点4加入到点集中。

第三步: 此时点集中新加入了点4,则以点4为出发点,从图中看到点3和点5与其相连,所以这一步需要更新D(3)和D(5)的值,D(3)= min{D(3), D(4)+ d(4,3)} ,即D(3) = min{60, 30+20} = 50;D(5) = min{D(5), D(4)+ d(4,5)} = min {100, 30 + 60} = 90。此时这一行其他数据不用变,此行更新完毕,找出未加入到点集中的 点3、点5 中的最小值,应该是点3,加入到点集中。

第四步,此时点集中新加入了点3,则以点3为出发点,发现点5与其相连,只需要更新D(5)即可。D(5) = min{D(5), D(3)+ d(3,5)} = min {90, 50 + 10} = 60,此时这行更新完毕,只有最后一个 点5 未加入到点集中了,所以将其加入。

第五步,此时点集中新加入了点5,则以点5为出发点,发现根本没有点与其相连,甚好,此行就不用再更新了。

第六步,机智的我发现所有点都被包含在了点集中,所以本次迪杰斯特拉算法就到此结束了。

剩下的就是代码实现了。

用一个二维数组d[i][j]来存从第i个点到第j个点的路径权重,其中65535为无穷大; 用一个一维数组f[i]才表示从第1个节点到第i个节点的最短路径。

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
46
47
48
49
50
/* 
*王欢 12283013
*实验四 编程实现路由算法
*/

public class Dijkstra_Router {
public static void main(String[] args) throws IOException {
Scanner scanner = new Scanner(System.in);
int i, j;
int n = scanner.nextInt();
//因为第0个单元我不用,所以就多开了两个空间
int[][] d = new int [n+2][n+2]; //二维矩阵存储点之间的距离
int []book = new int [n+2]; //标志数组,book[i]=0代表第i个点未在点集中,book[i]=1代表第i个点在点集中
int []f = new int[n+2]; //f[i]表示从第1个节点到第i个节点的最短路径
int min = 65535, min_pos = 0; //最小值设置为65535,为了比较出最小值, min_pos表示当前步骤中最小路径值的小标
for (i=0;i<n+2;i++) //初始化标志数组,并把第一个点添加到点集中,即book[1] = 1
book[i] = 0;
book[1] = 1;
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
d[i][j] = scanner.nextInt(); //读入二维矩阵,表示各个点的连接情况
for (i=2;i<=n;i++)
f[i] = d[1][i]; //按照上文所说的第一步进行初始化
System.out.println("运算过程:");
while (containsAllNodes(book, n)){
min = 65535; //每一步都要比较出最小值,所以记得在每一步的开始初始化一下最小值
for (i=2;i<=n;i++)
if (book[i] == 0 && f[i] < min){ //当第i个点未被加入到点集中 && f[i]<min
min = f[i];
min_pos = i;
}
book[min_pos] = 1; //找出当前步骤中最小值的位置为min_pos,即第min_pos个点加入到点集中,book[min_pos] = 1
for (i=1;i<=n;i++)
if (d[min_pos][i] != 65535) //根据上文讲解,f[i] = min{ f[i], f[min_pos] + d[min_pos][i] } 这一步是最重要的,一定要理解。比如上面讲解的第二步中,D(3)= min{D(3), D(2)+ d(2,3)},类比一下
f[i] = f[i] < (f[min_pos] + d[min_pos][i]) ? f[i] : (f[min_pos] + d[min_pos][i]);
for (i=1;i<=n;i++){
System.out.print(f[i] + " "); //打印本次运算结果
}
System.out.println();
}
System.out.println("最短路径: " + f[n]); //整个过程全部结束了,打印出第1个点到第n个点的最短路径
}
//判断是否所有点都被加入到点集中了
private static boolean containsAllNodes(int[] book, int n) {
for (int i=1;i<=n;i++){
if (book[i] == 0)
return true;
}
return false;
}
}

总结:如果可以熟练的手工算出那张动态表的话,就可以很好的理解迪杰斯特拉算法了。迪杰斯特拉本质上是一种动态规划,每次只能求出一个点到任意一个点的最短距离,而不是任意一个点到任意一个点的最短距离;同时又体现了贪心策略的思想,当一个新的点被加入到点集中时,下一步只需要更新与其直接相连(相邻)的点即可,而不是需要更新所有的点。至于使用什么语言来实现就都无所谓啦。还有如果需要记录最短路径所经过的节点,再增加相应数组编程实现即可。

###个人github: http://github.com/icodeu

###本例代码托管地址:https://github.com/icodeu/DijkstraForRouter

###CSDN博客:http://blog.csdn.net/icodeyou

###个人微信号:qqwanghuan 只为技术交流

image