求所有顶点的最短路径？
方法一：每次以一个顶点为源点，重复执行Dijkstra算法n次
方法二：(Floyd)弗洛伊德算法
Floyd算法思想
- 逐个顶点试探
- 从vi到vj的所有可能存在的路径中，因为某个顶点的加入，重新选出一条长度最短的路径。
算法步骤
- 初始时设置一个n阶方阵，令其对角线元素为0，若存在弧(vi,vj)，则对应元素为权值，否则无穷大。
各顶点之间的距离是直达的。
- 逐步试着在原直接路径中增加中间顶点，若加入中间顶点后路径变短，则修改之；否则，维持原值。所有顶点试探完毕，算法结束。
代码实现
matrix[i][j]表示从i到j的距离， 只有通过第3个位置，i和j之间的距离才有可能变短，我们设第3个位置为k
当k=1， matrix[i][j]的最短距离应该是Math.min(matrix[i][j], matrix[i][1] + matrix[1][j])， 注意是有向图，顺序很关键。
当k=2时， 可以通过两个点进行中转，k=1已经产生了结果，接下来只要看k=2是否会缩短距离即可，这是递推的过程， 我们可以运用动态规划自顶向下来分析。
先定义状态$f_k(i,j)$表示引入k个顶点，从i到j的最短路径，那么$f_{k-1}(i,j)$表示在不中转k的情况下i到j的最短路径，两种情况要么中转要么没中转，所以取最小值，状态转换方程如下：
$f_k(i,j)=min(f_{k-1}(i,j), f_k(i,j))$，$f_{k-1}(i,j)$就是$f(i,j)$,$f_k(i,j)=f[i][k] + f[k][j]$
核心代码就几行，主要是对递推公式的实现
1
2
3
4
5
6
7
8
9
|
public void floyd() {
for (int k = 0; k < vertexNames.size(); k++) {
for (int i = 0; i < vertexNames.size(); i++) {
for (int j = 0; j < vertexNames.size(); j++) {
matrix[i][j] = Math.min(matrix[i][k] + matrix[k][j], matrix[i][j]);
}
}
}
}
|
完整代码
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
101
102
103
104
|
package com.eh.ftd.dsa.ds;
import com.google.common.collect.Lists;
import java.util.Arrays;
import java.util.List;
/**
* 弗洛伊德算法
*
* @author David Li
* @create 2020/07/06 01:29
*/
public class Floyd {
private final static int INF = 999999;
/**
* 图的邻接矩阵表现形式
* 0表示自己指向自己，值为Integer.MAX_VALUE表示无穷远
*/
private int[][] matrix;
/**
* 顶点的表现形式
*/
private List<String> vertexNames;
public Floyd(List<String> vertexNames) {
this.matrix = new int[vertexNames.size()][vertexNames.size()];
this.vertexNames = vertexNames;
for (int i = 0; i < vertexNames.size(); i++) {
for (int j = 0; j < vertexNames.size(); j++) {
if (i != j) {
matrix[i][j] = 999999;
}
}
}
}
/**
* 获得顶点对应下标
*
* @param vertexName
* @return
*/
private int getIndexByVertexName(String vertexName) {
for (int i = 0; i < vertexNames.size(); i++) {
if (vertexName.equals(vertexNames.get(i))) {
return i;
}
}
throw new RuntimeException();
}
public void floyd() {
for (int k = 0; k < vertexNames.size(); k++) {
for (int i = 0; i < vertexNames.size(); i++) {
for (int j = 0; j < vertexNames.size(); j++) {
matrix[i][j] = Math.min(matrix[i][k] + matrix[k][j], matrix[i][j]);
}
}
}
}
public void printMatrix() {
for (int[] arr : matrix) {
System.out.println(Arrays.toString(arr));
}
}
/**
* 有向图
*
* @param v1
* @param v2
* @param weight
*/
public void buildEdge(String v1, String v2, int weight) {
int idx1 = getIndexByVertexName(v1);
int idx2 = getIndexByVertexName(v2);
matrix[idx1][idx2] = weight;
}
public static void main(String[] args) {
List cites = Lists.newArrayList("v0", "v1", "v2", "v3", "v4", "v5", "v6");
Floyd floyd = new Floyd(cites);
floyd.buildEdge("v0", "v1", 13);
floyd.buildEdge("v0", "v2", 8);
floyd.buildEdge("v0", "v4", 30);
floyd.buildEdge("v0", "v6", 32);
floyd.buildEdge("v1", "v5", 9);
floyd.buildEdge("v1", "v6", 7);
floyd.buildEdge("v2", "v3", 5);
floyd.buildEdge("v3", "v4", 6);
floyd.buildEdge("v4", "v5", 2);
floyd.buildEdge("v5", "v6", 17);
floyd.floyd();
floyd.printMatrix();
}
}
|
