DomBro Studio

动态规划-Floyed算法

2017/12/06

Floyed 算法

做一个 Floyed算法 的笔记,往往在算法前面加上一个英文名字就感觉很高大上,有一种听着就hin难的感觉。我尽可能写的通俗易懂,方便以后我忘了这个算法的时候,能以最快的速度唤醒的记忆。

what

Floyed算法 ,顾名思义一个叫 Floyed 的人发明的。这个算法具有很强的实际用用性,很多书上往往会用有向图这样的数据结构来讲解 Floyed算法,那我就反其道而行之吧!

一个场景

刚才说 Floyed算法 具有很强的应用性,那我就来举一个实际的例子将你带入。

如图,我们设定每两个地点之间的路线只能沿着箭头方向(生活中的单向车道),而有地点之间甚至没有路线,如果你想知道任意两个地点之间的最短路线咋办?告诉你 Floyed 算法就帮你达到这个目的!瞅啥呢赶紧上车!

场景格式化

还是刚才的场景中的图片,我们不妨按顺时针将每个地点编号,用数字表示他们的距离。比如体育馆到公园有2km的距离,我们把这句话变形为 : 1->2 = 2km 如此两两组合,我们不妨设一个二维数组(矩阵):
1)横坐标表示出发地,纵坐标表示目的地
2)坐标对应值就是出发地到目的地路线长度(注意这里加粗是因为所说的路线长度是考虑了方向的)
3)如果两地间没有路线我们将它的值看为无穷大(这是Floyed算法一个很重要的点)
4)如果两地是同一地点(横纵坐标相同),那它所代表的路径长度就是 0

如图,表格中第一列(横坐标)代表出发地,第一行代表目的地(纵坐标)。

问题分析

我们通过一个距离矩阵描述了场景中地点间的路径,使它可以由程序语言描述出来,事实上我们想做的是利用这个矩阵描述出地点间最短路径!还是要回到最开始的问题如果你想知道任意两个地点之间的最短路线咋办?这里Floyed算法给出了一个很明确的思路:利用中间地点! 有点生活常识的人都知道,有时候并不是两个地点的直接距离是最近的,就像图片中,家->学校 的路线比 家->体育馆->公园->学校 路线要远。这里所说的 体育馆、公园 就是中间地点,如果 出发地->目的地 的路线长度比 出发地 ->中间地点 ->目的地 的路线长度长,那就选取后者作为两地节点的最短路线。这也就是为什么,我们规定没有路线的两个地点间距离是无穷大的原因,是一个很好理解的解决方案。我们最终希望希望矩阵变成这个样子

how

知道了 Floyed算法的原理,来看下如何实现。

问题解决

上面说 Floyed算法 的核心思想就是要找一个中间地点,来比较经过中间地点的路线和直达线路的距离。可是如果有多个中间地点的路线怎么办?下面按照上图中地点的编号来代表地点,如果要知道 4 -> 3 的最短路线,我们就一定要知道 4 -> 3 的全部路线。这里有 4 -> 1 -> 3,4 -> 1 -> 2 -> 3,还有 4 -> 3 直达 三条线路,经过很简单的比较我们找出 4 -> 1 -> 2 -> 3 是最短的一条线路。经过这个例子,解决思路已经很清晰了:Floyed算法 在寻找任意两点最短路径时会将所有点作为中间点,依次比较 出发点->每个中间点的距离+每个中间点->目标点的距离 与 出发点->目标点的距离 大小,小的就是两点间最短距离,又由于设定没有路线的两点间距离为无穷大,所以我们总是可以通过中间点找到没有路线的两点间最短距。

核心代码

Floyed算法 的核心代码很简单,如果不考虑记录最短距离的路线,仅仅五行就够了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* @param disMatrix 记录两点间最短距离矩阵
* @param vertex 共有多少顶点(地点)
* @param pathMatrix 记录两点间最短路线的矩阵
*/
public static void floyed(int[][] disMatrix,int vertex,String[][] pathMatrix){

//这里的 K 表示中间顶点(元素),即从第一个顶点作为中间顶点循环找到最短路径
for (int k = 1; k <= vertex; k++){
for (int i = 1; i<= vertex; i++){
for (int j = 1; j <= vertex; j++){
//如果任何两个节点之间有一个中间节点使得两节点间的距离变得更短,那么就为其赋值为通过中间节点的路径和
//这里要注意的是还要判断起始和结束的节点到中间节点是不是通的,即 i->k 和 k->j 一定不能是无穷大
if (disMatrix[i][k] < Integer.MAX_VALUE && disMatrix[k][j] < Integer.MAX_VALUE && disMatrix[i][j] > disMatrix[i][k] + disMatrix[k][j]) {
disMatrix[i][j] = disMatrix[i][k] + disMatrix[k][j];
//只记录需要中间顶点的路径,如果不需要则是直达
pathMatrix[i][j] = "最短路径是节点 " + i + " —> 节点" + k + " —> 节点" + j;
}
}
}
}
}

代码会将初始的距离矩阵 int[][] disMatrix 变为两点间最短距离矩阵。

全部代码

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
public class DynamicProgram {


/**
* 初始化距离矩阵
* @param disMatrix 距离矩阵
* @param vertex 图的顶点个数
* @param paths 一共有多少条路径
*/
public static void initMatrix(int[][] disMatrix,int vertex,int paths){

/**
* 通过双重循环对距离矩阵初始化
*/
for (int i = 1;i <= vertex; i++){
for (int j = 1; j <= vertex; j++){
if (i==j)
//自己到自己的距离记为 0
disMatrix[i][j] = 0;
else
disMatrix[i][j] = Integer.MAX_VALUE;
}
}
/**
*
* 为图中路径赋值
*/
for (int i = 1; i <= paths; i++){
System.out.println("请输入起始点:");
Scanner scanner = new Scanner(System.in);
int begin = scanner.nextInt();
System.out.println("请输入终止点:");
int end = scanner.nextInt();
System.out.println("请输入节点"+begin+"和节点"+end+"的距离:");
int distance = scanner.nextInt();
disMatrix[begin][end] = distance;
}

}


/**
*
* @param disMatrix 记录两点间最短距离矩阵
* @param vertex 共有多少顶点点(地点)
* @param pathMatrix 记录两点间最短路线的矩阵
*/
public static void floyed(int[][] disMatrix,int vertex,String[][] pathMatrix){

//这里的 K 表示中间顶点(元素),即从第一个顶点作为中间顶点循环找到最短路径
for (int k = 1; k <= vertex; k++){
for (int i = 1; i<= vertex; i++){
for (int j = 1; j <= vertex; j++){
//如果任何两个节点之间有一个中间节点使得两节点间的距离变得更短,那么就为其赋值为通过中间节点的路径和
//这里要注意的是还要判断起始和结束的节点到中间节点是不是通的,即 ik 和 kj 一定不能是无穷大
if (disMatrix[i][k] < Integer.MAX_VALUE && disMatrix[k][j] < Integer.MAX_VALUE && disMatrix[i][j] > disMatrix[i][k] + disMatrix[k][j]) {
disMatrix[i][j] = disMatrix[i][k] + disMatrix[k][j];
pathMatrix[i][j] = "最短路径是节点 " + i + " —> 节点" + k + " —> 节点" + j;
}

}
}
}
}

public static void printDisMatrix(int[][] disMatrix,int vertex,String[][] pathMatrix){

for (int i = 1; i <= vertex; i++){
for (int j = 1;j <= vertex; j++){
if (i != j ){
String message = "节点"+i+"到节点"+j+"的最短距离为"+disMatrix[i][j]+" ";
if (pathMatrix[i][j] != null){
message += pathMatrix[i][j];
}else {
message += "最短路径为直接到达";
}
System.out.println(message);
}

}

}
}

public static void main(String[] args) {
System.out.println("请输入图中结点个数");
Scanner scanner = new Scanner(System.in);
int vertex = scanner.nextInt();
System.out.println("请输入图中路径的条数");
int paths = scanner.nextInt();
int disMatrix[][] = new int[10][10];
String[][] pathMatrix = new String[10][10];
initMatrix(disMatrix,vertex,paths);
floyed(disMatrix,vertex,pathMatrix);
printDisMatrix(disMatrix,vertex,pathMatrix);

}


}

运行结果

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
请输入图中结点个数
4
请输入图中路径的条数
8
请输入起始点:
1
请输入终止点:
4
请输入节点1和节点4的距离:
4
请输入起始点:
1
请输入终止点:
3
请输入节点1和节点3的距离:
6
请输入起始点:
1
请输入终止点:
2
...输入略...

节点1到节点2的最短距离为2 最短路径为直接到达
节点1到节点3的最短距离为5 最短路径是节点 1 —> 节点2 —> 节点3
节点1到节点4的最短距离为4 最短路径为直接到达
节点2到节点1的最短距离为9 最短路径是节点 2 —> 节点4 —> 节点1
节点2到节点3的最短距离为3 最短路径为直接到达
节点2到节点4的最短距离为4 最短路径是节点 2 —> 节点3 —> 节点4
节点3到节点1的最短距离为6 最短路径是节点 3 —> 节点4 —> 节点1
节点3到节点2的最短距离为8 最短路径是节点 3 —> 节点4 —> 节点2
节点3到节点4的最短距离为1 最短路径为直接到达
节点4到节点1的最短距离为5 最短路径为直接到达
节点4到节点2的最短距离为7 最短路径是节点 4 —> 节点1 —> 节点2
节点4到节点3的最短距离为10 最短路径是节点 4 —> 节点2 —> 节点3

about

总的来说 Floyed算法 是一个很好理解的算法,来分析一下。

时间复杂度

Floyed算法通过三重循环实现,时间复杂度可以看到是 O(N^3)。核心代码仅要五行,如果对时间复杂度要求不高,使用 Floyed算法求两点间最短距离 是一个很好的选择。

注意

Floyed算法 在使用上是有约束条件的,初始路径之间的距离不能出现负值,即如果如果把每个地点之间距离看成一个有向图,则该有向图顶点之间的权值不能为负。其实如果一个图中带有“负权回路”那么这个图则没有最短路径。

CATALOG
  1. 1. Floyed 算法
    1. 1.1. what
      1. 1.1.1. 一个场景
      2. 1.1.2. 场景格式化
      3. 1.1.3. 问题分析
    2. 1.2. how
      1. 1.2.1. 问题解决
      2. 1.2.2. 核心代码
      3. 1.2.3. 全部代码
      4. 1.2.4. 运行结果
    3. 1.3. about
      1. 1.3.1. 时间复杂度
      2. 1.3.2. 注意