我尝试了几种方法,但都以死胡同告终。 问题:
给定一个 G=(V,E) 有向未加权图,其中每个顶点都被着色为红色或蓝色。 设 V 中有顶点 s 和 t。描述一种算法,该算法将在 s 和 t 之间找到一条路径,该路径将包含最少的红色顶点。解释算法,证明它并显示它的复杂性。
我想到了两种方法,但都放弃了:
- 使用按颜色排序的邻接表(蓝色在前,红色在后)并运行 DFS - 坏主意
- 将红色顶点的每条边的权重设置为 2,将蓝色顶点设置为 1,然后运行 Dijkstra - 找到一个反例
我真的很乐意在正确的方向上得到一些帮助。我不希望获得完整答案,而是希望获得点击率/提示。
最佳答案
考虑为任何通往红色顶点的边设置 weight=1。然后显示从 s 开始的具有 n 个红色顶点的路径的成本是 n 或 n-1,具体取决于 s 的颜色。
关于algorithm - 查找具有 x 个红色顶点的 2 个顶点之间的路径,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15987614/