题目描述
Floyd 算法求最短路
算法1
(Floyd) $O(n^3)$
多源汇最短路问题,
基于动态规划的思想,采用领接矩阵来存储图,
f[k][i][j]
代表(k的取值范围是从1到n) 表示 从 i 这个点只经过 1 到 k 这些中间点,到达 j 的最短距离。
f[k][i][j] = min(f[k-1][i][j], f[k−1][i][k]+f[k−1][k][j])
从总结上来看,发现f[k]只可能与f[k−1]有关。
所以可以将 k 放在最外层循环并将维度降到 2 维。
时间复杂度
$O(n^3)$
参考文献
算法基础课
Java 代码
import java.io.*;
import java.util.*;
public class Main{
static int N=210;
static int n,m,k;
static int INF=0x3f3f3f3f;
static int g[][]=new int[N][N];
public static void floyd(){
for(int l=1;l<=n;l++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
g[i][j]=Math.min(g[i][j],g[i][l]+g[l][j]);
}
}
}
}
public static void main(String[] args) throws IOException{
BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
String[] strs=reader.readLine().split(" ");
n=Integer.parseInt(strs[0]);
m=Integer.parseInt(strs[1]);
k=Integer.parseInt(strs[2]);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j){
g[i][j]=0;
}else{
g[i][j]=INF;
}
}
}
int x,y,z;
for(int i=0;i<m;i++){
strs=reader.readLine().split(" ");
x=Integer.parseInt(strs[0]);
y=Integer.parseInt(strs[1]);
z=Integer.parseInt(strs[2]);
// 解决重边和自环的问题
g[x][y]=Math.min(g[x][y],z);
}
floyd();
for(int i=0;i<k;i++){
strs=reader.readLine().split(" ");
x=Integer.parseInt(strs[0]);
y=Integer.parseInt(strs[1]);
if(g[x][y]>INF/2){
// 我们这里的 INF 是用一个很大很大的数来代替无穷大,
//所以还是会被较小的数更新一下,
//所以,可以采用一个与 INF 相同量级的数即可.
System.out.println("impossible");
}else{
System.out.println(g[x][y]);
}
}
reader.close();
}
}