具有彩色邊的加權圖中的最短路徑

-1

我有一個帶有N個veritces和M個邊的帶權無向圖。每條邊都有其重量和顏色。整個圖表中最多有10種不同的顏色。每次我通過不同顏色的邊緣時，我必須支付額外的費用，等於K.給定兩個頂點A和B，我想找到它們之間的最短路徑。例如，給定具有3個頂點，K = 5和3個邊的多個圖：（權重3和顏色1的1→2），（權重5和顏色2的1→2），（2→3） 2和顏色2），最短路徑的權重是12.我想設計一個算法，可以在相當長的時間內解決這個問題（如O（N）或O（N log N）），但我不知道除了蠻力之外。具有彩色邊的加權圖中的最短路徑

我仍在尋找解決方案。如果有人知道如何解決它，請回復。

約束：

ň< = 10^5

中號< = 10^5

ķ< = 10^5

來源

2016-04-23 user128409235

交叉發表：http://cs.stackexchange.com/q/56688/755，http://stackoverflow.com/q/36808913/781723，http://mathoverflow.net/q/237582/37212 。請[不要在多個網站上發佈相同的問題]（http://meta.stackexchange.com/q/64068）。每個社區都應該誠實地回答問題，不要浪費任何人的時間。附：你遇到這種情況的背景是什麼？這是一個編程競賽的問題嗎？ –

我投票結束這個問題作爲題外話，因爲這是從這裏交叉發佈：http://cs.stackexchange.com/questions/56688/shortest-path-in-a-weighted-graph-with-彩色邊緣 –

我說你可以修改Dijkstra's Algorithm做這個。您只需爲傳遞的最後一個顏色的每個頂點存儲一個額外的字段，以便當算法需要邊的長度時，您可以在該邊的顏色不等於最後傳遞的顏色時添加顏色稅。然後，你必須更新該字段。這會在O（M + N log N）時間內完成。

編輯：隨着僞代碼：

1 function Dijkstra(Graph, source): 
2  dist[source] ← 0 
3 
4  create vertex set Q 
5 
6  for each vertex v in Graph:   
7   if v ≠ source 
8    dist[v] ← INFINITY 
9    prev[v] ← UNDEFINED 
11   Q.add_with_priority(v, dist[v]) 
12 
13  while Q is not empty: 
14   u ← Q.extract_min() 
15   for each neighbor v of u: 
16    if color(prev[u], u) ≠ color(u, v) 
17     alt = dist[u] + length(u, v) + colorTax 
18    else 
19     alt = dist[u] + length(u, v) 
20    if alt < dist[v] 
21     dist[v] ← alt 
22     prev[v] ← u 
23     Q.decrease_priority(v, alt) 
24 
25  return dist[], prev[]

原來，這與使用上一個場甚至沒有需要一個新的領域。

來源

2016-04-23 09:46:34

這是我的第一個想法，但我認爲它最終會是指數時間算法。如果我有一個非常大的圖，從頂點1有100個邊到頂點2和從頂點2到100邊到頂點3等。 – user128409235

我加入了一些僞代碼，我所做的更改不應該對運行產生任何影響時間，這被證明是O（M + N log N）。關於您對一個圖形的擔心，即在兩個頂點之間存在邊緣負載的情況下，您可以計算哪條邊的長度+可選的colorTax最低，然後使用該邊。這不應該太多地影響運行時間。除非你有大量的邊緣，但如果是這樣的話，無論如何你都不會有很好的運行時間。 –

如我在上一條評論中所解釋的，如果存在多條邊，則僞代碼沒有計算挑選哪條邊的方法。所以它不輸出12或15，它們在兩者之間不明確。正如我所提到的，當你做一些計算來找出哪條邊最小時，它會輸出12. –

對於每個頂點，根據您達到它的顏色（每個副本的傳出邊相同）將其分成10個不同的頂點。請注意，即使原始圖形是無向的，該新圖形也是定向的。

然後在這個新圖中Dijkstra的算法給你答案。

來源

2016-04-23 12:10:25 ffao

具有彩色邊的加權圖中的最短路徑

回答

相關問題