第6章 最短路径
第1节 只有五行的算法–Floyd-Warshall
任意两点之间的最短路径。
for(int k=1;k<=n;k++){ for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(e[i][j]>e[i][k]+e[k][j]){ e[i][j] = e[i][k]+e[k][j]; } } } }
第2节 Dijkstra算法–通过边实现松弛
从指定点到其余点的最短路径。“单源最短路径”。
基本思想是每次找到源点最近的一个顶点，然后以该顶点为中心进行扩展，最终得到源点到所有点的最短路径。
package ch6; import java.util.Scanner; public class Test2 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt();//n个顶点 int m = sc.nextInt();//m条边 final int inf = 999999; int [][] e = new int[10][10];//存储地图 //初始化e for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(i==j) { e[i][j] = 0; }else { e[i][j] = inf; } } } //读入边 for(int i=1;i<=m;i++) { int t1 = sc.nextInt(); int t2 = sc.nextInt(); int t3 = sc.nextInt(); e[t1][t2] = t3; } //初始化dis数组, 1到各个顶点的路程 int[] dis = new int[10]; for(int i=1;i<=n;i++) { dis[i] = e[1][i]; } //初始化book int[] book = new int[10]; book[1] = 1; //Dijkstra算法核心 for(int i=1;i<=n-1;i++) { int min = inf; int u = 1; //遍历，找到当前最小距离顶点u for(int j=1;j<=n;j++) { if(book[j]==0 &&dis[j]<min) { min = dis[j]; u=j; } } book[u] = 1; //通过u对其余顶点进行扩展 “松弛” for(int v=1;v<=n;v++) { if(e[u][v]<inf) { if(dis[v]>dis[u]+e[u][v]) { dis[v] = dis[u]+e[u][v]; } } } } //输出结果 for(int i=1;i<=n;i++) { System.out.print(dis[i]+" "); } } }
对于边数m小于n^2的稀疏图，可以用邻接表代替邻接矩阵，降低时间复杂度。
Scanner sc = new Scanner(System.in); int n = 5; int m = 4; int[] u = new int[m+1];//顶点（起点） int[] v = new int[m+1];//顶点（目的） int[] w = new int[m+1];//路程 //first和next在遍历顶点i的边时是第一条和下一条，但是存储时是最后一条和上一条。 //first[i]是顶点i的第一条边，有歧义。存储时是最近一次的读入顶点i位起点的边 int [] first = new int[n+1]; //next[i]是边i的下一条边。有歧义。存储时是上一次读入的顶点i为起点的边 int [] next = new int[m+1]; //初始化first ,-1代表顶点没有边 for(int i=1;i<=n;i++){ first[i] = -1; } //读入m条边 for(int i=1;i<=m;i++){ u[i] = sc.nextInt(); v[i] = sc.nextInt(); w[i] = sc.nextInt(); next[i] = first[u[i]]; first[u[i]] = i; } //遍历每个顶点的边 for(int i=1;i<=n;i++){ int k = first[i]; while(k!=-1){ System.out.print(""+u[k]+" "+v[k]+" "+w[k]+" "); k = next[k]; } }
第3节 Bellman-Ford —解决负权边
对所有的边进行n-1轮“松弛”操作。经过1轮松弛，得到的是从1号顶点“只能经过一条边”到其余各点的最短路径长度，经过2轮松弛，达到的是从1号顶点“最多经过2条边”到其余各点的最短路径长度。（不包含负权回路，负权回路时不存在最短路径）n个顶点的图中，任意两点之间最短路径最多包含n-1条边。因此，最多经过n-1轮松弛就能得到最短路径。
for(int k = 1; k<= n-1;k++){ for(int i = 1;i <= m;i++){ if(dis[v[i]]>dis[u[i]]+w[i]){ dis[v[i]]=dis[u[i]]+w[i]; } } }
第4节 Bellman-Ford的队列优化
每次仅对最短路径发生变化的点的邻边进行松弛，用队列记录这些发生变化的点。
选取队首顶点u,对u的出边进行松弛，松弛过程中用到的顶点v，把v加入队尾，同一个顶点不用重复加入。对u松弛完成后，将u出队列。接着对其余队首顶点进行重复上述操作。直到队列空为止。
package ch6; import java.util.Scanner; public class Test3 { public static void main(String[] args) { final int inf = 999999; Scanner sc = new Scanner(System.in); int n = sc.nextInt();//顶点数 int m = sc.nextInt();//边数 int[] u = new int[m+1];//顶点（起点） int[] v = new int[m+1];//顶点（目的） int[] w = new int[m+1];//路程 //first和next在遍历顶点i的边时是第一条和下一条，但是存储时是最后一条和上一条。 //first[i]是顶点i的第一条边，有歧义。存储时是最近一次的读入顶点i位起点的边 int [] first = new int[n+1]; //next[i]是边i的下一条边。有歧义。存储时是上一次读入的顶点i位起点的边 int [] next = new int[m+1]; //dis[i]是1号顶点到i号顶点的距离 int[] dis = new int[n+1]; for(int i=1;i<=n;i++) { dis[i] = inf; } dis[1] = 0; //book[i]为1表示i号顶点在队列中 int[] book = new int[n+1]; int[] que = new int[n+2]; int head = 1; int tail = 1; //初始化first ,-1代表顶点没有边 for(int i=1;i<=n;i++){ first[i] = -1; } //读入m条边 for(int i=1;i<=m;i++){ u[i] = sc.nextInt(); v[i] = sc.nextInt(); w[i] = sc.nextInt(); next[i] = first[u[i]]; first[u[i]] = i; } //1号顶点入队 que[tail] = 1; tail++; book[1] = 1; while(head<tail) { int k = first[que[head]];//队首顶点的第一条边 //松弛队首顶点的所有边 while(k!=-1) { if(dis[v[k]] > dis[u[k]]+w[k]) { dis[v[k]] = dis[u[k]]+w[k]; if(book[v[k]]==0) { que[tail]=v[k]; tail++; book[v[k]] = 1; } } k = next[k]; } //出队 book[que[head]]=0;//如果顶点最短路程估计值再次变小后，需要对其出边再次进行松弛 head++; } //输出到各点的最短路径 for(int i=1;i<=n;i++){ System.out.print(" "+dis[i]); } } }
测试数据： 5 7 1 2 2 1 5 10 2 3 3 2 5 7 3 4 4 4 5 5 5 3 6 结果： 0 2 5 9 9
第5节 最短路径算法对比分析
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-25AwzS6W-1589449758797)(C:\Users\LF\AppData\Roaming\Typora\typora-user-images\1589257208920.png)]
//输出到各点的最短路径 for(int i=1;i<=n;i++){ System.out.print(" "+dis[i]); } }
}
测试数据：
5 7
1 2 2
1 5 10
2 3 3
2 5 7
3 4 4
4 5 5
5 3 6
结果：
0 2 5 9 9
## 第5节 最短路径算法对比分析 [外链图片转存中...(img-25AwzS6W-1589449758797)]
