algorithm - 在不经过特定顶点的情况下找到最短路径

Question

给定一个有向未加权图 G，V 中蓝色顶点的集合 B 和 (V-B) 中的黄色顶点 y，我需要找到从给定源 s 到图中所有其他顶点的最短路径，无需访问访问蓝色顶点后的黄色顶点。换句话说，如果已经访问过蓝色顶点，则不允许访问黄色顶点(有可能某些顶点不可达)。

这是我的想法:

1. 以稍微不同的方式运行 BFS(s) - 如果我们经过 B 中的顶点 b，则不要继续搜索 b 的邻居。当 BFS 完成时，如果所有顶点都已标记，我们就完成了。否则:

2. 对 B 中的每个 b 运行 BFS(b)。对于从 b 到 y 的每条路径，删除路径中的最后一条边。例如，BFS(b) 找到路径 b,s,y 然后删除 (s,y)。

3. 运行 BFS。

复杂度为 O(|B||E|) 因为我们要运行 BFS(b) |B|次。

我觉得这个解决方案不是最好的，但这是我想出的。我错过了什么吗？

Answer 1

考虑两个图表:

1. A图包含除蓝色顶点以外的所有顶点和边
2. B图包含除黄色顶点外的所有顶点和边

现在从 A 图中的每个顶点(黄色顶点除外)到 B 图中相应的顶点添加一条有向边(权重为零)。

计算从A图中的源点到B图中的顶点的最短路径。

请注意，路径可以随时从 A 图形切换到 B 图形，但一旦切换就无法返回!这意味着路径可以使用黄色顶点，但前提是它从未访问过蓝色节点。