所有节点对之间的最短路问题

所有节点对之间的最短路问题（All Pairs Shortest Path）是一个经典的动态规划问题，它的目标是找到任意两个节点之间的最短路径。

假设有一个有向图 G，其中包含 n 个节点和 m 条有向边，每条边 (u, v) 的长度为 w(u, v)。我们需要计算任意两个节点之间的最短路径，即对于每一对节点 (i, j)，求出从节点 i 到节点 j 的最短路径长度。

Floyd 算法是一种经典的解决该问题的算法，它的基本思想是动态规划。具体来说，它使用一个二维数组 D 来保存节点之间的最短距离，其中 D(i, j) 表示从节点 i 到节点 j 的最短路径长度。初始时，D(i, j) 的值为节点 i 到节点 j 的边的长度；然后，对于每一个节点 k，我们检查从节点 i 到节点 j 的路径是否经过节点 k，如果经过，则尝试更新 D(i, j) 的值为 D(i, k) + D(k, j)。

Floyd 算法的时间复杂度为 O(n^3)，其中 n 表示节点的个数。虽然它的时间复杂度比较高，但是它的实现比较简单，而且对于任意两个节点之间的最短路径都可以求解，因此在实际应用中仍然具有一定的价值。