具有彩色邊緣的圖形中具有最少改變次數的路徑

Question

我有一個帶有彩色邊緣的有向圖（紅色爲&藍色），可能包含循環。問題是寫一個給定兩個頂點（s，t）的算法，找到s和t之間顏色變化最小的路徑（如果存在這樣的路徑）。 （我創建了一個新的圖，其中每個頂點對應於前一個圖的邊，並且包含邊的顏色，例如：if（1,2）是（1/2）是新圖中的一個頂點，我連接了「相鄰邊」頂點，新圖中改變顏色的邊的權重爲1，同一顏色變換爲0 ）。

我正在尋找線性時間（V和E）的解決方案。上面的一個在新圖中使用VxE邊。

有沒有這樣的解決方案來找到最小路徑？

Answer 1

第一階段：減少到最短路徑問題。

1. 對於每一個節點i我們創建了兩個節點i_red和i_blue。
2. 對於每個藍色邊緣i->j，我們創建兩條邊i_red->j_blue，重量爲1和i_blue->j_blue，重量爲0。
3. 我們以相似的方式處理紅色邊緣。
4. 我們還需要一個與start_red和start_blue連接的起始節點，連接權重爲0。
5. 與目標節點相似，目標節點與target_red和target_blue連接，權重爲0-連接。

現在，搜索從新創建的起始節點到新創建的目標節點的最短路徑。節點數是原始圖中的兩倍，邊的數量是原始圖的兩倍，因此減少量是線性的。

後您減少問題的最短路徑搜索，你可以做到以下幾點：

1. 步驟：僅在重0邊，處理圖形的無向一個與BFS可以幫助以線性時間查找此0邊圖中的所有組件。

2. 步驟：在圖表上運行BFS其中來自前一步驟的部件膠合在一起作爲超級節點，因此，所有邊緣具有權重1和BFS會發現的最短路徑。

顯然，這種算法的所有三個部分（在0-邊圖形BFS，膠合組件以超級節點和在所得到的曲線圖中的BFS）中線性時間運行。