假定我得到一个简单的有向非负加权图G =（V，E）和一个顶点X⊂V的子集。该图以邻接列表表示，子集X作为列表。我如何找到一种算法来计算图中不属于X的顶点s，t之间的短路路径，并且每当路径在X中使用两个顶点时，这两个之间至少存在一个不在X中的顶点顶点？该算法应为O（m + nlogn）时间。
我已经考虑了很长时间，但是找不到O（m + nlogn）时间以下的算法，知道如何处理吗？
假设m = |E|和n = |V|。
Dijkstra的带有Fibonacci堆的算法在O(m + n log n)中运行。因此，您想考虑额外的约束而不增加最终时间的复杂性。
如果无法在恒定时间内查询顶点是否在X中，那么首先需要通过在O(n)中建立X的哈希集来做到这一点。使用此哈希集的后续查询将在恒定时间内运行。
现在，从图形中删除X中的成对顶点之间的边仅增加了另一个O(m)。然后，您可以在删除边缘的新图上运行Dijkstra的图，整个过程只需要O(m + n log n)时间。