问题

用Floyd算法求解下图各个顶点的最短距离。写出Floyd算法的伪代码和给出距离矩阵（顶点之间的最短距离矩阵）

从任意节点i到任意节点j的最短路径不外乎2种可能:

1是直接从i到j，2是从i经过若干个节点k到j。

所以，我们假设dis(i,j)为节点u到节点v的最短路径的距离，对于每一个节点k，我们检查dis(i,k) + dis(k, j) < dis(i,j)是否成立，如果成立，证明从i到k再到j的路径比i直接到j的路径短，我们便设置dis(i,j) = dis(i,k) + dis(k,j)，这样一来，当我们遍历完所有节点k，dis(i,j)中记录的便是i到j的最短路径的距离。

解析

给定一个n个点m条边的有向图，图中可能存在重边和自环，边权可能为负数。

再给定k个询问，每个询问包含两个整数x和y，表示查询从点x到点y的最短距离，如果路径不存在，则输出“impossible”。

数据保证图中不存在负权回路。

设计

void floyd(){for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}

分析

算法时间复杂度:O(n3)

源码

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=210,INF=1e9;
int n,m,k,d[N][N];
void floyd(){for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
int main(void){cin>>n>>m>>k;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){if(i==j)d[i][j]=0;else d[i][j]=INF;}for(int i=0,a,b,c;i<m;i++){cin>>a>>b>>c;d[a][b]=min(d[a][b],c);}floyd();for(int i=0,x,y;i<k;i++){cin>>x>>y;if(d[x][y]>INF/2)cout<<"impossible"<<endl;else cout<<d[x][y]<<endl;}return 0;
}