找到属于图的两个不相交子集的任意两个节点之间的最短路径

存在一个无向图，其中每个节点都被分配了一些颜色。我必须找到从任何蓝色节点到任何红色节点的最短路径。（其他颜色也可能存在于图中，尽管它并不重要，但不知道有多少颜色存在。）我怎样才能在多项式时间内做到这一点？找到属于图的两个不相交子集的任意两个节点之间的最短路径

来源

2012-03-14 anirudh

我相信Dijkstra算法可以用某种方式来解决这个问题，但是我一直无法弄清楚。 – anirudh 2012-03-14 19:25:12

作为提示，在图中添加两个新节点 - 称它们为s和t。将s连接到每个成本为0的边的蓝色节点，并将每个红色节点连接到成本为0的边。然后找到从s到t的最短路径。

希望这会有所帮助！

来源

2012-03-14 19:26:27 templatetypedef

谢谢，这确实是解决方案。 – anirudh 2012-03-14 19:36:01

多项式既用于添加s和t节点，也用于找到它们之间的最短路径（例如用Dijkstra），因此它是多项式。 – pvoosten 2012-03-14 19:42:10

@lbp在多项式时间中有很多简单的方法可以解决它，你可以做Floyd-Warshall并找到最小距离的对（蓝色，红色）。你可以做Dijkstra | red | * |蓝色|次，效率非常低，仍然是多项式。但是这个答案给出了一个有效的方法，不仅是多项式。 – sdcvvc 2012-03-14 20:45:45

找到属于图的两个不相交子集的任意两个节点之间的最短路径

回答

相关问题