Floyd Warshall 有约束
Floyd Warshall with constraints
我想知道是否可以使用带约束的 floyd warshall 意味着假设您有一组大小为 logn 的“特殊顶点”并且您想要计算所有最短路径但每条路径必须至少经过一个“特殊顶点”这甚至是可能的还是很难 np
是的，您甚至可以将 Floyd–Warshall 算法用作黑盒，并结合 post 处理步骤来实现此目的。
首先，使用 Floyd–Warshall 算法计算每对顶点之间的最短路径。然后，对于每对顶点 u 和 v 以及每个特殊顶点 w，计算两条最短路径的总和，即从 u 到 w 和从 w 到 v 的那个。从 u 到 v 的约束最短路径由特殊顶点 w 实现，该顶点最小化 u-w 路径的长度和 w-v 路径的长度。
由于特殊顶点的个数显然最多n，所以post-处理步骤的计算复杂度为O(n^3)。因为Floyd-Warshall算法的计算复杂度也是O(n^3)，所以这个算法的总计算复杂度是O(n^3).
我想知道是否可以使用带约束的 floyd warshall 意味着假设您有一组大小为 logn 的“特殊顶点”并且您想要计算所有最短路径但每条路径必须至少经过一个“特殊顶点”这甚至是可能的还是很难 np
是的，您甚至可以将 Floyd–Warshall 算法用作黑盒，并结合 post 处理步骤来实现此目的。
首先，使用 Floyd–Warshall 算法计算每对顶点之间的最短路径。然后，对于每对顶点 u 和 v 以及每个特殊顶点 w，计算两条最短路径的总和，即从 u 到 w 和从 w 到 v 的那个。从 u 到 v 的约束最短路径由特殊顶点 w 实现，该顶点最小化 u-w 路径的长度和 w-v 路径的长度。
由于特殊顶点的个数显然最多n，所以post-处理步骤的计算复杂度为O(n^3)。因为Floyd-Warshall算法的计算复杂度也是O(n^3)，所以这个算法的总计算复杂度是O(n^3).