找到有向非负加权图的最短路径，避免给定子集顶点的任何顶点彼此相邻？
Find the shortest path of a directed non-negative weighted graph avoiding any vertices of a given subset vertices to be next to each other?
假设我有一个简单的有向非负加权图 G = (V, E) 和一个顶点子集 X ⊂ V。该图是邻接表表示，子集 X 是一个列表。
我如何找到一种算法来计算图中不属于 X 的顶点 s、t 之间的短路，并且每当该路径使用 X 中的两个顶点时，这两个顶点之间至少有一个不在 X 中的顶点顶点？该算法应该在O(m+nlogn)时间内。
我已经考虑这个问题很长时间了，但找不到 O(m+nlogn) 时间的算法，知道我该如何处理这个问题吗？
假设 m = |E| 和 n = |V|。
Dijkstra 算法在 O(m + n log n) 中具有斐波那契堆 运行s。所以你想在不增加最终时间复杂度的情况下考虑额外的约束。
如果无法在常量时间内查询一个顶点是否在 X 中，那么您首先需要通过在 O(n) 中构建 X 的哈希集来实现。使用此哈希集的后续查询将在恒定时间内 运行。
现在，从图中移除 X 中顶点对之间的边只会添加另一个 O(m)。然后，您可以 运行 Dijkstra 在这个新图上删除边，整个过程只需要 O(m + n log n) 时间。
假设我有一个简单的有向非负加权图 G = (V, E) 和一个顶点子集 X ⊂ V。该图是邻接表表示，子集 X 是一个列表。 我如何找到一种算法来计算图中不属于 X 的顶点 s、t 之间的短路，并且每当该路径使用 X 中的两个顶点时，这两个顶点之间至少有一个不在 X 中的顶点顶点？该算法应该在O(m+nlogn)时间内。
我已经考虑这个问题很长时间了，但找不到 O(m+nlogn) 时间的算法，知道我该如何处理这个问题吗？
假设 m = |E| 和 n = |V|。
Dijkstra 算法在 O(m + n log n) 中具有斐波那契堆 运行s。所以你想在不增加最终时间复杂度的情况下考虑额外的约束。
如果无法在常量时间内查询一个顶点是否在 X 中，那么您首先需要通过在 O(n) 中构建 X 的哈希集来实现。使用此哈希集的后续查询将在恒定时间内 运行。
现在，从图中移除 X 中顶点对之间的边只会添加另一个 O(m)。然后，您可以 运行 Dijkstra 在这个新图上删除边，整个过程只需要 O(m + n log n) 时间。