在C++中找到最短路徑權重

Question

我正在嘗試編寫一個C++代碼 ，它在計算優先級後選擇某個特定路徑 ，它會選擇具有最高優先級的路徑。

但我有最短路徑的另一個代碼，我正在合併我的代碼 選擇最小權重的路徑！

問題是： 我該如何更改我的代碼給出最高優先級的路徑，最低的重量數！ 而不改變標誌。 （我不wan't有負數！」

Answer 1

如果你的目標是讓最短路徑具有最高優先級，你可以代表新的重量1 /優先。這樣，你的算法會選擇的路徑，你經歷所有邊的總和爲您提供了一個高優先級。

小心不要與maximum capacity problem混淆的問題。 例如，如果有從A到B 2點的路徑，與給出每條邊的優先次序：

A - 60 - > X1 - 60 - > X2 - 60 - >乙

或

A - 100 - > X1 - 50 - > X2 - 100 - > B

請確保您希望您的算法選擇1/100 + 1/50 + 1/100 = 0.04的第二條路徑，但您僅通過50或優先級，而不是1/60 + 1/60 + 1/60 = 0.05的路徑，但您所經歷的最低優先級的值爲60

---

另一種選擇，如果你知道圖表中的最高邊緣優先MAX_PRIORITY（比方說，這是100），你不希望處理浮點數：

你能代表你的體重爲（MAX_PRIORITY + 1-優先級）（（101-優先級））。這樣，你不會有任何負數。