我想知道是否可以使用带有约束的 floyd warshall ，这意味着假设您有一组大小为 logn 的“特殊顶点”，并且您想要计算所有最短路径，但每条路径必须至少经过一个“特殊顶点”这是否可能或者很难 np
最佳答案
是的，您甚至可以使用 Floyd–Warshall 算法作为黑匣子，并结合后处理步骤来实现此目的。
首先，使用 Floyd–Warshall 算法计算每对顶点之间的最短路径。然后，对于每对顶点 u 和 v 以及每个特殊顶点 w，计算两条最短路径的总和，即来自 u 到 w 以及从 w 到 v 的一个。从 u 到 v 的受约束最短路径是通过特殊顶点 w 实现的，它最小化了 u 的总和-w 路径的长度和 w-v 路径的长度。
由于特殊顶点的数量显然最多为n，因此后处理步骤的计算复杂度为O(n^3)。由于Floyd-Warshall算法的计算复杂度也是O(n^3)，因此该算法的总计算复杂度为O(n^3)。
关于algorithm - 弗洛伊德·沃歇尔(Floyd Warshall)受到限制，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/65425817/