找到屬於圖的兩個不相交子集的任意兩個節點之間的最短路徑

存在一個無向圖，其中每個節點都被分配了一些顏色。我必須找到從任何藍色節點到任何紅色節點的最短路徑。（其他顏色也可能存在於圖中，儘管它並不重要，但不知道有多少顏色存在。）我怎樣才能在多項式時間內做到這一點？找到屬於圖的兩個不相交子集的任意兩個節點之間的最短路徑

來源

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

找到屬於圖的兩個不相交子集的任意兩個節點之間的最短路徑

回答

相關問題