我已经尝试了几种方法，但它们都以死胡同告终。问题：
给定一个 G=(V,E) 一个有向无权图，其中每个顶点都被着色为红色或蓝色。假设有来自 V 的顶点 s 和 t。描述一个算法，该算法将找到 s 和 t 之间的路径，该路径将包含最少的红色顶点。解释算法，证明它并展示它的复杂性。
我想到了两种方法并放弃了两种方法：
我真的很乐意在正确的方向上获得一些帮助。我不想得到完整的答案，而是得到点击/提示。
考虑为任何到达红色顶点的边设置 weight=1。然后证明从 s 出发的具有n 个红色顶点的路径的成本是n或n-1，具体取决于 s 的颜色。
好吧，在我向他展示了加权的方法之后，我找到了这个问题的答案，不是我，而是我的一个朋友。
我们将使用 2 个队列，而不是在 BFS 算法中使用一个队列：一个用于蓝色顶点，一个用于红色顶点。
我们检查 S 是什么颜色并将其添加到正确的队列中，只要蓝色顶点的队列不为空，我们就从它中出列并继续常规 BFS，如果遇到红色顶点，我们将其加入红色队列，如果我们找到一个蓝色顶点，我们将它排入蓝色队列。如果蓝色队列为空，我们从红色队列中出列。
最终，数组 pi[|V|] 将保持对顶点 v 的反向表示，其中红色顶点最少。
由于 BFS 算法并没有对其数据结构进行真正的更改，因此正确性证明成立，并且时间复杂度为 O(|V|+|E|)，就像 BFS 中一样。
谢谢你们的帮助！