全源最短路径 - floyd算法 - O(N ^ 3)

2024-03-19 04:12:34

Floyd-Warshall算法的原理是动态规划。

设D_i,j,k为从i到j的只以(1..k)集合中的节点为中间节点的最短路径的长度。

若最短路径经过点k，则D_i,j,k = D_{i,k,k − 1} + D_{k,j,k − 1}；
若最短路径不经过点k，则D_i,j,k = D_{i,j,k − 1}。

因此，D_i,j,k = min(D_{i,k,k − 1} + D_{k,j,k − 1},D_{i,j,k − 1})。

for (k = ; k <= n; k++)  //经过编号为前k个的顶点

{

    for (i = ; i <= n; i++)

    {

        for (j = ; j < i; j++)

        {

                if ( == A[i][k] ||  == A[k][j])

                    continue;

                if ( == A[i][j] || A[i][k] + A[k][j] < A[i][j])

                    A[i][j] = A[j][i] = A[i][k] + A[k][j];

        }

    }

}

最新文章

热门文章