任意两点间的最短路问题(Floyd-Warshall算法)

求解所有两点间的最短路的问题叫做任意两点间的最短路问题。

只使用顶点0 ~ k和i, j的情况下，记 i 到 j 的最短路长度为d[ k + 1][ i ] [ j ]。k = -1时，认为只是用 i 和 j，所以d[0][ i ][ j ] = cost[ i ][ j ]。接下来，把只使用顶点0 ~ k的问题归约到只使用0 ~ k - 1的问题上。

只使用0 ~ k时，分 i 到 j 的最短路正好经过顶点k一次和完全不经过顶点k两种情况讨论：

1. 不经过顶点k的情况下，d[ k ][ i ][ j ] = d[ k - 1][ i ][ j ]。
2. 通过顶点k的情况下，d[ k ][ i ][ j ] = d[ k - 1 ][ i ][ k] + d[ k - 1 ][ k ][ j ]。

综合，得到了d[ k ][ i ][ j ] = min(d[ k - 1 ][ i ][ j ], d[ k - 1 ][ i ][ k ] + d[ k - 1 ][ k ][ j ])

也可以将此DP简化为d[ i ][ j ] = min(d[ i ][ j ], d[ i ][ k ] + d[ k ][ j ])。

代码：

int d[MAX_V][MAX_V];  //d[u][v]表示边e=(u, v)的权值 
int V;

void warshall_floyd() {
    for(int k = 0; k < V; ++k) {
        for(int i = 0; i < V; ++i) {
            for(int j = 0; j < V; ++j) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
}