目录
- 只有五行算法的—Floyd-Warshall
- Dijkstra算法—单源最短路
- 代码实现
- 邻接表
- Bellman-Frod-解决负权边问题
- Bellman_Frod的优化
- 最短路径算法对比分析
**多资源路径问题：**求任意两点之间的的最短路径
**代码基本思想：**最开始只允许经过1号顶点进行中转，接下来只允许经过1号和2号顶点进行中转…允许经过1-n号所有顶点进行中转，求任意两点之间的最短路程。用一句话概括就是：从i号顶点到j号顶点只经过前面k号点的最短路径。其实这是一种“动态规划“的思想。
package ch6;
import java.util.Scanner;
public class Floyd_Warshall {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();//顶点的个数
int m = scanner.nextInt();//两个顶点之间的条数
int[][] e = new int[n+1][n+1];
int t1,t2,t3;
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] = 9999;
}
}
//读入边
for (int i =1;i<=m;i++){
t1 = scanner.nextInt();
t2 = scanner.nextInt();
t3 = scanner.nextInt();
e[t1][t2] = t3;
}
scanner.close();
floyd_washall(n,e);
for (int i =1; i<= n;i++){
for (int j =1; j<=n;j++){
System.out.print(e[i][j] + " ");
}
System.out.println();
}
}
public static int[][] floyd_washall(int n,int[][] e){
for (int k =1;k<=n;k++){
for (int i =1; i<= n;i++){
for (int j=1;j<=n ;j++){
//加上<9999的判断条件，就可以不用计算无法到达的边和可以达到的边之和-7
if (e[i][k] < 9999 && e[k][j] < 9999 & e[i][j] > e[i][k] + e[k][j])
e[i][j] = e[i][k] + e[k][j];
}
}
}
return e;
}
}
它的时间复杂度为O(N3)
Dijkstra算法—单源最短路算法：指定一个点到其余各个顶点的最短路径，也叫做单源最短路
需要用一个数组dis来存储1号顶点到其余各顶点的初始路程
| 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|
| dis | 0 | 1 | 12 | ∞ | ∞ | ∞ |
此时dis数组中的值称为最短路径的”估计值“。
算法的基本思想：每次找到离源点最近的一个顶点，然后以该顶点为中心进行扩展，最终得到源点到其余所有点的最短路径。基本步骤如下：
1.将所有的顶点分为两个部分：已知最短路程的顶点集合P和位置最短路径的顶点集合Q。最开始，已知最短路径的顶点集合P中只有源点一个顶点。我们在这里用一个book数组来记录哪些点在集合P中。
2.设置源点s到自己的最短路径为0即dis[s] = 0。若存在有源点能直接到达的顶点i，则把dis[i]设为e[s] [i]。同时把所有其他顶点的最短路径设为∞
3.在集合Q的所有顶点中选择一个离源点s最近的顶点u(即dis[u]最小)加入到集合P。并考察所有以点u为起点的边，对每一条边进行松弛操作。例如，如果存在一条从u到v的边，那么可以通过将边u→v添加到尾部来扩展一条从s到v的路径，这条路径的长度是dis[u] + e[u] [v]。如果这个值比目前已知的dis[v]的值要小，我们就可以用新的值来代替当前dis[v]中的值。
4.重复第三步，直到Q为空，算法结束
代码实现package ch6;
import java.util.Scanner;
public class Dijkstra {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] e = new int[n][n];
int[] dis = new int[n];
int[] book = new int[n];
int t1,t2,t3;
int min;
int max = 9999999;
int u = 0,v;
for (int i =0;i dis[u] + e[u][v]){
dis[v] = dis[u] + e[u][v];
}
}
}
}
for (int i =0;i
时间复杂度为O(N2)
邻接表
package ch6;
import java.util.Scanner;
public class Sparse {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[] u = new int[m+1];
int[] v = new int[m+1];
int[] w = new int[m+1];
int[] first = new int[n+1];
int[] next = new int[m+1];
//初始化frist数组
for(int i =1 ;i<= n;i++){
first[i] = -1;
}
for (int i =1; i<=m ; i++){
u[i] = scanner.nextInt();
v[i] = scanner.nextInt();
w[i] = scanner.nextInt();
//first[u[i]]代表第i条边
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.println(u[k] + " " + v[k] + " " + w[k]);
k = next[k];
}
}
}
}
Bellman-Frod-解决负权边问题
package ch6;
import java.util.Scanner;
public class Bellman_Ford {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[] dis = new int[n];
int[] u = new int[m];
int[] v= new int[m];
int[] w= new int[m];
int max = 99999;
for (int i =0; i< m;i++){
u[i] = scanner.nextInt();
v[i] = scanner.nextInt();
w[i] = scanner.nextInt();
}
//初始化dis
for (int i =0; i dis[u[j]] + w[j])
dis[v[j]] = dis[u[j]] + w[j];
}
}
//输出
for (int i =0; i
package ch6;
import java.util.Scanner;
public class Bellman_Ford {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[] dis = new int[n];
int[] u = new int[m];
int[] v= new int[m];
int[] w= new int[m];
int max = 99999;
int flag = 0;
for (int i =0; i< m;i++){
u[i] = scanner.nextInt();
v[i] = scanner.nextInt();
w[i] = scanner.nextInt();
}
//初始化dis
for (int i =0; i dis[u[j]] + w[j]) {
dis[v[j]] = dis[u[j]] + w[j];
check = 1;//如果发送了改变则为1
}
}
if(check ==0 ) break;//如果没有发生更新数组则退出循环
}
for (int i =0; i dis[u[i]] + w[i])
flag = 1;
}
//输出
for (int i =0; i
Bellman_Frod的优化
- 每次仅对最短路估计值发生变化了的顶点的所有出边执行松弛操作
- 首先把所有的顶点和边建立邻接表
- 建立一个队列数组，每次选取队首的顶点u，对顶点u的所有出边进行松弛操作，如果u->v这这条边使得源点到v的最短路程变短，则v入队
- 同一个顶点多次入队是毫无意义的，所以要利用book数组判断是否重复
- 对顶点u的所有边进行松弛操作后，u出队
- 循环操作直到队列变空
package ch6;
import java.util.Scanner;
public class Bellman_Ford_optimize {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[] u = new int[m+1];
int[] v = new int[m+1];
int[] w = new int[m+1];
int[] dis = new int[n+1];
int[] book = new int[n+1];
int[] first = new int[n+1];
int[] next = new int[m+1];
int[] que = new int[10];//比n的值大就可以
int max =9999;
int head = 1,tail = 1;
for (int i =1; i<=n;i++){
dis[i] = max;
}
dis[1] = 0;
//初始化book数组
for (int i =1; i<= n;i++){
book[i] = 0;//表示每个顶点都不在队列当中
}
//初始化first数组
for (int i =1;i<= n;i++){
first[i] = -1;//表示每一个顶点都没有对应的边
}
for (int i =1;i<=m;i++){
u[i] = scanner.nextInt();
v[i] =scanner.nextInt();
w[i] = scanner.nextInt();
//下面是建立邻接表的关键
next[i] = first[u[i]];
first[u[i]] = i;
}
//1号顶点入队
que[tail] = 1;tail++;//后移
book[head] = 1;//标记
while(head dis[u[k]] +w[k]){
dis[v[k]] = dis[u[k]] + w[k];//更新顶点1到顶点v[k]的路程
//这的book数组用来判断定点给v[k]是否在队列当中
//如果不适用这样一个数组来标记的话，那么每一次都要从头开始遍历队列，浪费时间
if(book[v[k]] ==0){
que[tail] = v[k];
tail++;
book[v[k]] = 1;
}
}
k = next[k];//取出下一条边
}
//出队
book[que[head]] = 0;//把出队列的顶点置为0，方便下一次入队
head ++;
}
for (int i =1; i<=n;i++){
System.out.println(dis[i]);
}
}
}
最短路径算法对比分析 
