floyd

问题: 可以处理负权路吗

允许负权，但是不能有负环。因为有负环的话，转一次负环最短路就会减少，那么无穷无尽，没有最短路的概念，
所以只能判段负环的存在而不能求这个图中两点间的最短路。Floyd正确性的证明就是，假设只经过前k个点的两点间最
短路已知，那么接下来只经过前 k + 1 个点的任意两点的最短路都可能由它松弛得到。很显然负权没有影响到动态
规划的这个过程。

floyd 判断负权环( 很少用 因为有 spfa )

bool floyd(){
    for(int k = 1;k <= n;k ++ ){
        for(int i = 1;i <= n;i ++ ){
            for(int j = 1;j <= n;j ++ ){
                if(dist[i][j] > dist[i][k] + dist[k][j]){
                    dis[i][j] = dis[i][k] + dis[k][j];
                }
            }
            if(dis[i][i] < 0) return true;
        }
    }
    return false;
}

bellman

bellman_ford算法可以存在负权回路，因为它求得的最短路是有限制的，是限制了边数的，这样不会永久的走下去

应用

1. 最短路 牛的旅行

最大直径: 原图中的最大直径， 加完边之后的这条边成为最大直径

ans = max(maxd[i], min(maxd[i] + maxd[j] + dist[i][j]));

2. 传递闭包 排序

1. 每次求一遍传递闭包，然后判断，如果d[i][i] 无解，如果最后都没有判断出来就是不确定，否则就是有唯一解
2. 每次求一边topsort ，如果有环则无解， 如果有多个起点就是 不确定， 否则就有唯一解，按照拓扑序输出就行

3. 正权图的最小环 观光之旅

1. k 是 i->j 的最大编号
2. 如果有最小环 那么 ans = d[k - 1][i][j] + w[i][k] + w[k][j] 而 k - 1 层的刚好就是上次迭代后的结果

4. floyd变形 + 倍增 求恰好经过 k 条边的最短路径 牛站

PS: bellman_ford 算法求的是最多经过 k 条边的最短路 和 floyd 的不一样，
    也可以用 spfa 来求，但是和普通的 spfa 不太一样

spfa 可以参考: orz