在附加條件下查找最快路徑

我在想，如果Dijkstra的算法在無向圖中存在多個直接連接時能正常工作。在附加條件下查找最快路徑

例如爲：

enter image description here

我想用Dijkstra算法來找出最快的路徑，但有一個附加條件。邊上所有additional_data的和不能大於= x。所以，如果它出現重量的邊緣：3使用不當，我的程序會嘗試第二個邊緣。

編輯：我的任務是找到最快的路徑，在附加條件下，來自邊緣的additional_data的總和不能高於x。你能告訴我如何處理這個問題嗎？

EDIT2：（上賞金設置）

我一直在研究互聯網很多，直到我發現這個link。有一個解釋如何做我要求的東西。（高級中級 acapite）

我試圖用它以某種方式2天，但我擔心我不明白這個算法正確。我想問你們中的一些人來幫助我解決這個問題，通過解釋我一些例子（幾個第一步）。這裏的例子：

enter image description here

來源

2013-01-06 Patryk

平行邊緣不會破壞Dijkstra，但附加條件會。 –

這是一個確切的重複，但原來的問題沒有解決方案 - 只有一個解決方案存在於其他地方的聲明（以及SPOJ中的815個人找到了一個）。 – LSerni

這是*不是*完全重複 - 另一個問題甚至沒有提到在一對節點之間可能存在兩條或更多路徑的可能性，也沒有提到附加條件附加到下襬的可能性。 –

我想你可以修改Dijkstra的算法來處理這個問題。 Dijkstra的算法基本上是通過遞增地構建列出每個節點的最短路徑的表來工作的。您將創建一張表，列出給定成本的每個節點的最短路徑。或者說，在一個給定的成本或更少，即在一個給定的預算。

更正式地說，您可以將原始圖轉換爲另一個圖，然後將Dijkstra應用於該圖。假設additional_data成本始終是一個整數，該變換是：

以每原始節點n並創建一組節點（N，C），用於從0℃的每個整數值到的值預算（您可以容忍的additional_data的最大總和）

取權重w和additional_data a的每個原始連接n1 - > n2，並創建一組從每個節點（n1，c）到節點（n2， c + a），每個都有重量w

原始圖模型中的節點在空間中的位置。變換後的圖模型中的節點位於狀態空間中，狀態變量是位置，以及目前花費的預算金額。

如果你想從A到Z得到x的預算，那麼你只需使用Dijkstra的算法來找到從（A，0）到其中一個節點（Z，c < = x）的路由。

編輯：我已經實現了修改的Dijkstra算法：https://bitbucket.org/twic/roadsproblem。關鍵是在src/solver.py。

來源

2013-01-06 18:02:26

老實說，我並沒有真正明白你的意思。假設我的max_sum = 200.我是否需要將每個節點轉換爲變換圖中的200個節點集？ – Patryk

是的。那麼，不。從「更正式」來說，我正在描述一些簡單的工作方式，這可以很容易地證明你想要做的事情是可能的。我不會那樣實現它。相反，我會按照我在第一段中所說的，我意識到我沒有清楚地解釋過，但是這等於懶洋洋地構建了變換圖。 –

我很高興能更詳細地解釋這一點，也許有一些代碼，但我必須出去吃晚飯。也許以後！ –

你的附加條件使得問題變得更加困難。看看它，我認爲你唯一能做的就是找出源頭和目標之間的所有可能路徑，按總邊權重對它們進行排序，然後逐個檢查是否有附加條件。

但是，查找兩個頂點之間所有可能路徑的問題是NP-Hard。稍微修改過的DFS版本可能可以做到這一點，但可能不是所有情況。

來源

2013-01-06 17:55:52 kokx

我不認爲Dijkstra的算法是一個很好的解決方案，因爲所需的距離不僅是源節點和目的地。下面是基於A *搜索算法的解決方案。\

首先，進行基於weight一個FolydWarshall然後根據additional_data得到爲圖表中的每個節點對的至少weight和至少additional_data。

FloydWarshall(Weights); 
    FloydWarshall(Additional_datas);

第二，我們執行*搜索基於優先級隊列中的一個與像下面的結構元素（用C代碼的例子。）的優先級隊列將自動至少獲得weights_sum在所有候選人。 weights_expected是通過當前節點到目的節點的路徑的最好的猜測而weights_now是目前體重

struct NODE 
    { 
     int node; 
     int weights_expected; 
      int weights_now; 
     int additional_datas_now; 
      bool visited; 
    }; 
    bool operator < (const NODE &A,const NODE &B) 
    { 
     return A.weights_expected>B.weights_expected || (A.weights_expected==B.weights_expected && 
    A.additional_datas_now>B.additional_datas_now); 
    }

在A *搜索算法，

1) we first put the source node into priority queue. 
    2) while Priority Queue is not empty: 
     Set **A** equal to the head of priority queue and pop out the head of priority queue. 
     A.visited=True; 
     if A is the destination node **Dest**, **return** A.weights_expected. 
     For each neighbors **B** of node **A**, 
      if A.visited==False **and** A.additional_datas_sum+|AB|.additional_data+Additional_datas[B][Dest]<=x, 
       1) B.additional_datas_now=A.additional_datas_now+|AB|.additional_data;  
       2) B.weights_now=A.weights_now+|AB|.weight; 
       3) B.weights_expected=B.weights_now+Weights[B][Dest]; 
       3) push node B into priority Queue. 
    3) Print "Do not find a proper path" //if code came to here, that means the if in 2) do not return a value.

A *搜索將仍然NP困難的，因爲在最差它必須搜索每個可能的路徑。但是，它將比簡單的DFS搜索更快，並執行大量的搜索路徑剪切。

來源

2013-01-07 21:30:14

您可以在它們之間創建一個節點的副本，並添加第二個可能的路徑。

像這樣（僞）

Node 1____ 
|   | 
|path1 | 
|cost=3 |path2 cost=5 
|   | 
Node 2____/

變成這樣：

Node 1____cost=0____Node 1a 
|   path 1a  | 
|path1    |path2 
|cost=3    |cost=5 
|      | 
Node 2________________/

不知道這是否會工作，但它是一個想法。

來源

2013-01-11 23:45:58 Codeman

下面是對您找到的算法如何處理您的示例問題的解釋。

問題是要找到node one和node four之間的最短路徑，並且額外的條件是沿途的累計成本不應超過7。

我們想要找到的解決方案是首先從node one到節點node two，距離爲190，代價爲4。然後使用距離195和成本3的路徑從node two到node four。總共路徑的距離爲385，成本爲7。

步驟1

那麼如何算法找到這個？第一步就像你所做的那樣設置矩陣minArray(i,j)。數組中的元素(i,j)包含您必須前往節點j並保持i剩餘金額的距離。

Original array.

起步沒有訪問元素和，因爲我們已開始在node one與7「資金」左上角元素設置爲零。上表中的空白空間對應於數組中設置爲infinity的值。

步驟2

接下來，我們發現在陣列的最低值，這是在(remaining money, node) = (7,1)位置零。此元素設置爲visited（使用與minArray相同大小的矩陣visitedArray跟蹤元素的狀態），這意味着我們已選擇node one。現在，所有連接到node one的節點都會通過遍歷相應的邊來更新值。

Array one.