如何找到最短的彩色路徑？

給定G =（V，E）每條邊都有這三種顏色{綠，紅，藍}中的一種。如果他擁有所有三種顏色，我們稱之爲「彩色路徑」。如何找到最短的彩色路徑？

Input: graph G(V,E),weight function w:E->Q+ , colored edges and vertices s . 
    output: algorithm that finds for every vertices v, a shortest path from s 
      that is Colored path

我的解決方案是通過圖形行走，計數每個頂點的路徑具有顏色數。創建名爲G1，G2的圖形的3個拷貝，G3

對於每一個信息v C（V）= 2（c是從s的顏色編號，以該路徑）連接V1的第二曲線（G2）到V2與邊緣權重= 0。

對於每個邊緣c（v）= 3從邊緣權重= 0的v2（從G2）到v3（到G3）連接。

將dijkstra從s運行到t3（在G3中）。

我的解決方案是否正確？

來源

2017-01-30 elias rizik

與'古典'全對最短路徑問題不同的是，可能存在頂點「u」，「v」，其中根本沒有從u到v的彩色路徑，即使圖已連接;由於邊的類別，問題似乎也不容易分解，因爲彩色路徑可以分解爲不是彩色路徑的路徑。 – Codor

你能舉一個更詳細的建築例子嗎？ – Codor

你的算法的描述是沒有意義的。什麼是「每邊c（v）= 3」？什麼是「從s到這個路徑的顏色數量」？ – user31264

對我來說看起來不正確。

最簡單的方法是認識到，在正常的Dijkstra中，每個節點只存儲一件重要的事情，那就是從根開始的絕對最短路徑長度。

使用彩色路徑，您必須存儲每個顏色組合的最短路徑長度。因此，對於3種顏色，您必須存儲最短的紅色路徑，最短的藍色路徑，最短的綠色路徑，以及最短的紅藍綠色路徑，最後是最短的紅綠色路徑 - 藍色路徑。（共有7種顏色組合）。

來源

2017-01-30 13:28:52 MSalters

似乎是正確的，解釋是非常有見地的。不知何故，我期待這個問題在複雜性方面更難。爲了更加簡潔：Dijkstra的算法適用於單一來源版本，而不是全部版本。 – Codor

@Codor：公平點; Dijkstra對於所有路徑都是低效的。 – MSalters

如何找到最短的彩色路徑？

回答

相關問題