Floyd求最短路
不同于前面的最短路,属于单元汇,求的是1号点到各个点的最短路。
Floyd求的是x
号点到y
号点的最短路,属于多元汇最短路问题。
dist[i][j]
存的是i
号点到j
号点的最短距离。
将邻接矩阵转换为最短距离矩阵,查表即可。
实现代码
3重for循环实现
for(int k=1;k<=n;k++){
//先循环k,i,j顺序可颠倒。
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dist[i][j]=Math.min(dist[i][j],dist[i][k]+dist[k][j]);
}
}
}
其本质是一个动态规划问题:
dist[k,i,j]=dist[k-1,i,k]+dist[k-1,k,j];
理解:
i点到j点经过1到k条边的距离
=i点到k点经过1到k-1条边的距离+k点到j点经过1到k-1条边的距离
由于两段距离都经过1到k-1个点,类似于dp优化,计算时保存的是上一层的值,所以可以将这一重给省略掉。
变为二维:
dist[i][j]=Math.min(dist[i][j],dist[i][k]+dist[k][j]);
时间复杂度
3层for循环:每层循环走n个点
O(n^3)
代码
import java.util.*;
public class Main{
static int n,m,q;
static int INF=0x3f3f3f3f;
static int N=210;
static int dist[][]=new int[N][N];
public static void floyd(){
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dist[i][j]=Math.min(dist[i][j],dist[i][k]+dist[k][j]);
}
}
}
}
public static void main(String []args){
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
m=sc.nextInt();
q=sc.nextInt();
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j)dist[i][j]=0;
//不存在负权回路,处理自环,自己指向自己默认为0
//不影响更新其他点的距离
else{
dist[i][j]=INF;
}
}
}
while(m-->0){
int a=sc.nextInt();
int b=sc.nextInt();
int w=sc.nextInt();
dist[a][b]=Math.min(dist[a][b],w);
//处理重边,保留最小的边权即可
}
floyd();
while(q-->0){
int a=sc.nextInt();
int b=sc.nextInt();
if(dist[a][b]>INF/2)System.out.println("impossible");
//边权为负,存在某些点到点的距离比INF要小一些
//需要大于INF/2
else System.out.println(dist[a][b]);
}
}
}