最短路算法(1)
介绍floyd:
用于求全源最短路径的算法，这个代码非常简短好记，这里会记录两种应用。
1.简单模板优化以及处理连通性问题
这个算法可以用来求传递闭包（注释中有）。
代码如下：
const int N = 100+50;
const int INF = 500;//这个不可以太大，如果太大，那么D[i][k]+D[k][j]可能会溢出
int D[N][N];
void floyd(int n){
for(int k = 1;k <= n;k++)
for(int i = 1;i <= n;i++)
//if(G[i][k]!=INF) 一个优化加速
for(int j = 1;j <= n;j++)
D[i][j] = min(D[i][j],D[i][k]+D[k][j]);//这个可以优化加速
//对于连通性的题目，把数值变成o和1来表示联通与否
//如果把上一句话变成D[i][j] = D[i][j]||(D[i][k]&&D[k][j]),就可以用来求传递闭包
cout< } D数组的解释： 从i号顶点到j号顶点只经过前k号点的最短路程。 事实上，D数组本来应该是f[k][x][y]，这表示为： 经过前k个点从x到y的最短路径 这个数组的解法是： D[k][x][y] = min(D[k-1][x][y],D[k-1][x][k]+D[k-1][k][y]); 也就是经过k是否可以让x,y更短 这是我们发现，若删掉第一维不影响结果，也就是说第一维是无意义的。 得到状态转移方程： D[x][y] = min(D[x][y],D[x][k]+D[k][y]); 2.最小环 现在我们看一个应用: 利用floyd求解最小环问题： 假设有n个顶点，m条边，如何求解在一个图中权值和最小的环？ 先考虑暴力解法： 在删掉u的每一条邻边(u,v)，在计算u到v的最短路，再加上原来的(u,v),这样得到一条最小环。这需要枚举m条边，求最短路的时间复杂度可以优化到(n+m)logn ,这样整体的时间复杂度就是O (m(n+m)logn)。 使用floyd算法是可以解决这个问题的： floyd有这样一个性质： 在最外层循环到点 k 时（尚未开始第 k 次循环），最短路数组 D 中，D[u][v] 表示的是从 u到v且仅经过编号在 [1,k) 区间中的点的最短路。 那么对于最短路(u,v)，最小环就应该是dis[u][v]加上另外的一个点，记作w。 对于(u,v)来说状态方程就是： ans = min(ans,dis[u][v] + weight[u][w]+weight[w][v]) 代码如下： for(int k = 1;k < = n;k++){ for(int i = 1;i <= k;i++) for(int j = 1;j <= k;j++) ans = min(ans,dis[u][v] + weight[u][w]+weight[w][v]); for(int i = 1;i <= n;i++) for(int j = 1;j <= n;j++) dis[i][j] = dis[i][k]+dis[k][j]; }