最短路径算法（1）

最短路算法(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[1][n]<<endl;
}

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];
}