有一个无向图，每个节点都被赋予一些颜色。我需要找到从任何一个蓝色节点到任何一个红色节点的最短路径。（图中可能存在其他颜色，虽然这并不重要，但不知道有多少种颜色）。如何在多项式时间内完成这个问题？
在一个图中找到任意两个属于两个不相交子集的节点之间的最短路径。
5
- anirudh
1
1我相信 Dijkstra 算法可以用来解决这个问题，但我还没有找到如何做到的方法。 - anirudh
1个回答
7
作为提示，向图形中添加两个新节点- 将它们称为 s 和 t。将 s 与每个蓝色节点连接，成本为 0，并将每个红色节点连接到 t，成本为 0。然后找到从 s 到 t 的最短路径。
希望这可以帮助！
希望这可以帮助！
- templatetypedef
2
多项式时间复杂度既适用于添加s和t节点，也适用于在它们之间查找最短路径（例如使用Dijkstra算法），因此它是多项式的。 - pvoosten
2@lbp 有很多简单的方法可以在多项式时间内解决它，你可以使用 Floyd-Warshall 算法找到距离最小的一对 (blue,red)。你也可以使用 Dijkstra 算法进行 |red| * |blue| 次计算，虽然效率低下，但仍然是多项式时间。但这个答案提供了一种高效的方式，不仅是多项式时间。 - sdcvvc
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接