Floyd 算法¶

Floyd 算法，使用动态规划来求解所有点对之间的最短路径。

设给定图的顶点集合 $V=\{1,2,\cdots,n\}$ 和边集合 $E$ ，定义函数 $f(k,u,v)$ ，表示只允许经过顶点 $V'=\{1,2,\cdots,k\}$ ，顶点 $u$ 到顶点 $v$ 的最短路径长度（ $u$ 和 $v$ 不一定在 $V'$ 中）。

当 $k=0$ 时，

f(0,u,v) = \begin{cases} 0 & \text{如果 } u = v \\ +\infin & \text{如果 } u \neq v \text{ 且 } (u,v) \notin E \\ w(u,v) & \text{如果 } u \neq v \text{ 且 } (u,v) \in E \end{cases}

当 $k>0$ 时，

f(k,u,v) = \min \big(f(k-1,u,v), f(k-1,u,k)+f(k-1,k,v)\big)

当 $k=n$ 时， $f(n,u,v)$ 就是顶点 $u$ 到顶点 $v$ 的最短路径长度。

实现¶

/**
 * Floyd's algorithm.
 *
 * @param graph graph[u][v] is the length of the edge from u to v or {@code -1} if there is no edge.
 */
int[][] floyd(int[][] graph) {
    int n = graph.length;
    int[][] dp = new int[n][n];
    for (int u = 0; u < n; u++) {
        for (int v = 0; v < n; v++) {
            dp[u][v] = graph[u][v];
        }
    }

    for (int k = 1; k < n; k++) {
        for (int u = 0; u < n; u++) {
            for (int v = 0; v < n; v++) {
                if (dp[u][k] == -1 || dp[k][v] == -1) {
                    continue;
                }
                if (dp[u][v] == -1) {
                    dp[u][v] = dp[u][k] + dp[k][v];
                } else {
                    dp[u][v] = Math.min(dp[u][v], dp[u][k] + dp[k][v]);
                }
            }
        }
    }
    return dp;
}

算法的时间复杂度为 $O(n^3)$ 。

Floyd 算法¶

实现¶

参考¶