algorithm - 查找具有 x 个红色顶点的 2 个顶点之间的路径

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 的颜色。