找出有x个红色顶点的两个顶点之间的路径

Question

我尝试了几种方法，但都以死胡同告终。问题:

给定一个G=(V,E)，其中每个顶点都是红色或蓝色的有向无权图。假设v中有顶点s和t，描述一种算法，能找到s和t之间的路径，使红色顶点最少。解释算法，证明它，并显示它的复杂性。

我想到了两种方法，都放弃了:

1. 使用按颜色排序的邻接表(蓝色第一，红色最后)并运行DFS -坏主意
2. 将红色顶点的每条边的权重设置为2，蓝色顶点为1，然后运行Dijkstra -找到一个反例

我真的很乐意得到一些正确方向的帮助。我不希望得到完整的答案，而是点击/提示。

Answer 1

考虑为任何指向红色顶点的边设置weight=1。然后证明从s出发的具有n红色顶点的路径的代价是n或n-1，取决于s的颜色。

Answer 2

我找到了这个问题的答案，不是我，而是我的一个朋友，在我向他展示了加权方法之后。

在BFS算法中不使用一个队列，我们将使用两个队列:一个用于蓝色顶点，一个用于红色顶点。

我们检查S的颜色并将其添加到正确的队列中，只要蓝色顶点的队列不为空我们就从队列中退出并继续常规的BFS如果我们遇到红色顶点我们将其排队到红色队列中如果我们找到蓝色顶点我们将其排队到蓝色队列中。如果蓝色队列为空，则退出红色队列。

最终数组pi[|V|]将保存一个指向顶点V的反向表示，其中红色顶点最少。

由于BFS算法和它的数据结构没有真正的改变，所以正确性的证明是成立的，时间复杂度是0 (|V|+|E|)，就像BFS一样。

谢谢大家的帮助!