不经过特定顶点找到最短路径

Question

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

我的想法如下：

1. 以稍微不同的方式运行BFS（s）- 如果我们通过在B中的顶点b，不继续搜索b的邻居。当BFS完成时，如果已标记所有顶点，则我们完成。否则：

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

3. 运行BFS（s）。

时间复杂度将是O（|B|*|E|），因为我们将运行BFS（b）|B|次。

我觉得这个解决方案可能不是最好的，但这就是我想出来的。我有遗漏什么吗？

- amitooshacham

---

在第三步，可能存在另一条从s经过y的路径，因此这种方法不正确。即使您完全删除y，您的算法仍将无法处理像这样的图形。您需要采用完全不同的方法。 - BlueRaja - Danny Pflughoeft

@BlueRaja-DannyPflughoeft，我不明白为什么我的算法在你给出的例子上不起作用。在你的例子中，算法在第一步完成，因为我们运行BFS（s），并且我们从s获取所有最短路径（当我说“如果我们经过一个在B中的顶点b，则不要在b的邻居上继续搜索”时，我并不是指我们应该完全停止BFS，而是不在b上继续BFS，而在其余部分继续）。 - amitooshacham

Answer 1

考虑两个图：

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

现在，在A图中，对于每个顶点（除了黄色顶点），添加一条指向B图中相应顶点的零权重有向边。

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

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

- Peter de Rivaz