我想知道是否可以使用带有约束的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)。