0%

最短路径

前言

最短路径算法一般是广搜算法。有多种情况,单源最短路径,多源最短路径,负权回路等问题

多源最短路径Floyd-Warshall算法

  • 优点:实现简单,代码量少
  • 缺点:时间复杂度为O(n^3),不能解决负权回路的问题

使用邻接矩阵存储法存储图

遍历每个节点作为中转点,取距离的最小值
比如1到3,a[1][3]=6
以2作为中转点,即a[1][2]+a[2][3]=5<a[1][3]

伪代码

1
2
3
4
5
6
7
8
9
10
function floyd(map, length) {
var i,j,k;
for(k for 0 to length){//k为中转点,每个点都可以是中转点
for(i for 0 to length){//起点i
for(j for 0 to length){//终点j
map[i][j] = min(map[i][j], map[i][k]+map[k][j]);
}
}
}
}

单源最短路径Dijkstra算法

假设有一个数组 dis[],存储第一个点能到达的所有点的距离,{0,1,12,∞,∞,∞},
那么, dis[] 就是 第一个点1 到达所有点的最短距离。
dis[]{0,1,12,∞,∞,∞}

dis[]数组可以看出, 距离第一个点1最近的点是第二个点2, 将其作为中转点。
再从矩阵map[2][j]中获取所有与第二个点B邻接的点, 即第三个点3第四个点4,
dis[j]加上3、42的距离,如果小于最小值dis[j], 则更新dis[j]的值。
dis[]{0,1,10,4,∞,∞}

再找dis[]数组的最小点, 因为点2已经使用过了, 所以选择 点4作为中转点。
dis[]{0,1,8,4,17,19}

以此类推
点3作为中转点, dis[]{0,1,8,4,13,19}
点5作为中转点, dis[]{0,1,8,4,13,17}
还剩下最后一个 点6, 没必要找了, 因为没有另一个点可以到达了。

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
public class Main{
private static int MAX_STEP = 1000;
public static void main(String[] args) throws Exception {
Scanner in = new Scanner(System.in);
int n = in.nextInt();//顶点数
int m = in.nextInt();//边数
int[][] map = new int[n+1][n+1];//存储图的邻接矩阵
boolean[] book = new boolean[n+1];//标记某个点是否走过
int[] dis = new int[n+1];//存储最短距离的数组
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++){
if(i==j) map[i][j] = 0;
else map[i][j] = MAX_STEP;

}
}
for(int i = 1; i <= m; i++){
map[in.nextInt()][in.nextInt()] = in.nextInt();
}
for(int i = 1; i <= n; i++){
dis[i] = map[1][i];
}
//初始化完毕

book[1] = true;
for(int i = 1; i <= n-1; i++){//遍历第1到n-1个点
int min = MAX_STEP;
int next = 0;
for(int j = 1; j <=n; j++){//找到距离第i个点最近的一个点作为中转点
if(book[j]==false && dis[j]<min){
min = dis[j];
next = j;
}
}
book[next] = true;
for(int j = 1; j <= n; j++){//根据中转点获得新的距离,用来更新dis
dis[j] = Math.min(dis[j], dis[next]+map[next][j]);
}
printf(dis);
}
}

private static void printf(int[] arr){
for(int i = 0; i < arr.length; i++){
System.out.print(arr[i]+" ");
}
System.out.println("");
}
}

另外还有邻接表存储图的算法(看不懂, 弃了)

单源最短路径Bellman-Ford算法

和Dijkstra算法一样, 假设有一个数组 dis[],
存储第一个点能到达的所有点的距离,{0,∞,∞,∞,∞,∞},
那么, dis[] 就是 第一个点0 到达所有点的最短距离。
dis[]{0,∞,∞,∞,∞,∞}, 注意这里和Dijkstra算法不一样。

扫描第一条边0 1 1, 点0点1 的权值为 1
因为 点0是起点, 所以原先的dis[0]+第一条边的权值w[1]<原先的dis[1], 也就是0+1<∞
通过第一条边, 可以把 dis[]更新为{0,1,∞,∞,∞,∞}

扫描第二条边0 2 12, 点0点2 的权值为 12
因为 点0是起点, 所以原先的dis[0]+第二条边的权值w[2]<原先的dis[2], 也就是0+12<∞
通过第一条边, 可以把 dis[]更新为{0,1,12,∞,∞,∞}

扫描第三条边1 2 9, 点1点2 的权值为 9
因为 点1是起点, 所以原先的dis[1]+第三条边的权值w[3]<原先的dis[2], 也就是1+9<12
通过第一条边, 可以把 dis[]更新为{0,1,10,∞,∞,∞}

依次类推,
扫描第4条边1 3 3, dis[]数组{0,1,10,4,∞,∞}
扫描第5条边2 4 5, dis[]数组{0,1,10,4,15,∞}
扫描第6条边3 2 4, dis[]数组{0,1,8,4,15,∞}
扫描第7条边3 4 13, dis[]数组{0,1,8,4,15,∞}
扫描第8条边3 5 15, dis[]数组{0,1,8,4,15,19}
扫描第9条边4 5 4,dis[]数组{0,1,8,4,15,19}

第一轮扫描完毕, 一共要扫描 顶点数-1轮。
因为任意两点之间最多包含顶点数-1条边。

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
public class Main {
public static void main(String[] args) {
/**
6 9
0 1 1
0 2 12
1 2 9
1 3 3
2 4 5
3 2 4
3 4 13
3 5 15
4 5 4
*/
Scanner in = new Scanner(System.in);
int n = in.nextInt(), m = in.nextInt();
int[] dis = new int[n]; // 第0个顶点距离其他顶点的距离
int[] u = new int[m];// 第i条边的起点
int[] v = new int[m];// 第i条边的终点
int[] w = new int[m];// 第i条边的权值

for(int i = 0; i < m; i++){
u[i] = in.nextInt();
v[i] = in.nextInt();
w[i] = in.nextInt();
}
dis[0] = 0;
for(int i = 1; i < n; i++){
dis[i] = 999;
}
// 初始化完毕

boolean equals = false;
int[] backupDis = new int[m];

// 扫描 顶点数-1 轮
for(int k = 0; k < n-1 && !equals; k++){
backup(dis, backupDis); // 备份距离数组
for(int i = 0; i < m; i++){
dis[v[i]] = Math.min(dis[v[i]], dis[u[i]]+w[i]); // 扫描每条边, 更新dis数组
}
equals = equals(dis, backupDis); // 扫描后dis数组是否有变化, 没有则已经是最短路径
}

boolean isLoop = false;
for(int i = 0; i < m && !isLoop; i++){
if(dis[v[i]] > dis[u[i]]+w[i]){
isLoop = true; // 如果还能继续更新, 说明有负权回路
}
}
System.out.println(isLoop?'有':'无'+"负权回路");

if(!isLoop){
System.out.println(Arrays.toString(dis));
}

}


private static void backup(int[] src, int[] backup){
System.arraycopy(src, 0, backup, 0, src.length);
}

private static boolean equals(int[] src, int[] other){
if(src.length!=other.length) return false;

for(int i = 0, len = src.length; i < len; i++) {
if(src[i]!=other[i]) return false;
}
return true;
}
}

总结

算法 单、多源 算法核心 空间复杂度 时间复杂度 适用情况
Floyd-Warshall 多源 中转点 O(N^2) O(N^3) 稠密图, 解决负权回路
Dijkstra 单源 中转点 O(M) O((M+N)logN) 稠密图
Bellman-Ford 单源 O(M) O(NM) 稀疏图, 解决负权回路
很高兴得到您的赞赏