通过至少一个特定类型顶点的最短路径算法
Shortest path algorithm that passes through at least one of a particular type of vertex
我有一个包含大约 6500 个顶点的图，其中一些具有标签 'c'。我需要设计一种算法，找到至少包含这些 'c' 个顶点中的一个的任意两个顶点之间的最短路径。这很简单，但问题是所需的复杂度为 O(ElogV)，其中 E 是边数，V 是顶点数。我已经使用最小堆实现了 Dijkstra 算法，因此我可以在 O(ElogV) 中找到一般最短路径，但我无法扩展问题。有什么建议吗？
请注意，迭代地调用 Dijkstra 从源到 c + c 到目标不属于复杂性限制，因为它最终是 O(CElogV)
设 G 为您的图，顶点为 v1...vn。
创建一个包含原始顶点的两个副本的新图形：v1..vn、v1'..vn'。在这个新图中，如果原始图中 vi 和 vj 之间有一条边，则让 vi 和 vj 或 vi' 和 vj' 之间有一条边。如果原始图中 vi 和 vj 之间有一条边，并且 vj' 标记为 c.
，则还让 vi 和 vj' 之间有一条边
那么，给定两个顶点vi，vj，新图中vi和vj'之间的最短路径是原图中vi和vj之间至少经过一个标记为c的顶点的最短路径。
因为新图中的顶点数翻了一番，边数最多翻了三倍，所以复杂度不会从O(VlogE)改变（其中V和E是vertices/edges在原图中）。
如果你有一个无向图：
假设您正在搜索 S 和 T 之间的最短路径。
- 使用 Dijkstra 算法找到从 S 到任何节点的所有最短路径
- 找到从 T 到任何节点的所有最短路径（相同算法）
- 遍历所有标记的节点 c 并使用先前计算的最短路径找到 S 到 c 与 c 到 T 的最短路径。
我有一个包含大约 6500 个顶点的图，其中一些具有标签 'c'。我需要设计一种算法，找到至少包含这些 'c' 个顶点中的一个的任意两个顶点之间的最短路径。这很简单，但问题是所需的复杂度为 O(ElogV)，其中 E 是边数，V 是顶点数。我已经使用最小堆实现了 Dijkstra 算法，因此我可以在 O(ElogV) 中找到一般最短路径，但我无法扩展问题。有什么建议吗？
请注意，迭代地调用 Dijkstra 从源到 c + c 到目标不属于复杂性限制，因为它最终是 O(CElogV)
设 G 为您的图，顶点为 v1...vn。
创建一个包含原始顶点的两个副本的新图形：v1..vn、v1'..vn'。在这个新图中，如果原始图中 vi 和 vj 之间有一条边，则让 vi 和 vj 或 vi' 和 vj' 之间有一条边。如果原始图中 vi 和 vj 之间有一条边，并且 vj' 标记为 c.
，则还让 vi 和 vj' 之间有一条边那么，给定两个顶点vi，vj，新图中vi和vj'之间的最短路径是原图中vi和vj之间至少经过一个标记为c的顶点的最短路径。
因为新图中的顶点数翻了一番，边数最多翻了三倍，所以复杂度不会从O(VlogE)改变（其中V和E是vertices/edges在原图中）。
如果你有一个无向图：
假设您正在搜索 S 和 T 之间的最短路径。
- 使用 Dijkstra 算法找到从 S 到任何节点的所有最短路径
- 找到从 T 到任何节点的所有最短路径（相同算法）
- 遍历所有标记的节点 c 并使用先前计算的最短路径找到 S 到 c 与 c 到 T 的最短路径。