有一个无向图，其中每个节点都分配了一些颜色。我必须找到从任何蓝色节点到任何红色节点的最短路径。 (图中也可能存在其他颜色，虽然这无关紧要，但不知道有多少种颜色。)如何在多项式时间内完成？
最佳答案
作为提示，向图中添加两个新节点 - 称它们为 s 和 t。将 s 连接到成本为 0 的边的每个蓝色节点，将每个红色节点连接到成本为 0 的边的 t。然后找到从 s 到 t 的最短路径。
希望这对您有所帮助!
关于algorithm - 找到属于图的两个不相交子集的任意两个节点之间的最短路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9708735/