我試圖在加權多向圖中找到最短路徑（最便宜的），其中頂點是城市，邊是城市之間的路線，權重是價格。
每條路線/邊緣都歸 3 家公司之一所有。公司擁有的所有邊的價格都相同。因此，“A”公司擁有的所有邊的價格都是 X。
因此，如果最終路徑經過 A 公司的 2 條路線和 B 公司的 1 條路線，則最終價格為 2 PriceofA 1 PriceOfB。此外，邊緣的權重只是關聯公司的價格。
到目前為止，這是正常情況，但是，以下額外規則使我感到困難：
第 3 家公司“C”無論最終路徑中有多少條路線，都只應用一次價格，但它的價格通常高于前幾家公司。因此，C 的路線最適合較長的路徑，而 A 和 B 的路線最適合較短的路徑。
這是我到目前為止所做的（以及為什么它不起作用）：
我正在使用 Dijkstra 來獲得最便宜的路徑，我只是將每個邊的權重設定為公司的價格。即使對于 C.
然后，如果演算法訪問 C 擁有的節點，則將 C 擁有的所有其他邊的權重設定為 0。否則演算法繼續正常運行。
問題是 Dijkstras 演算法總是優先考慮直接的最佳選擇，并且由于公司 A 和 B 的價格比 C 小，那么它會盡量避開 C。有時這會導致演算法認為最短/最便宜的路徑，但是實際上，如果它從一開始就選擇 C，本可以便宜得多。
在這種情況下，我怎樣才能獲得真正最便宜的路徑？
我應該改用另一種演算法嗎？如果有，是哪一個？
uj5u.com熱心網友回復：
這里的一種選擇是轉換原始航班圖，直接編碼這樣的想法，即一旦您乘坐了 C 航班，所有未來的 C 航班都是免費的。
對于每個機場 x，創建兩個節點 x 1和 x 2。這個想法是節點 x 1對應于在機場 x 中但從未乘坐過 C 航班，而 x 2對應于在機場 x 中至少乘坐過一次 C 航班。
現在添加邊緣如下。對于從機場 x 到機場 y 的價格為 p 的每個 A 或 B 航班，添加一條從 x 1到 y 1價格 p 和從 x 2到 y 2價格 p 的邊。這些對應于以既定價格乘坐 A 和 B 航班。然后，對于從機場 x 到機場 y 的價格為 p 的每個 C 航班，添加從價格為 p 的 x 1到 y 2的邊（這是您支付使用 C 航班的一次性成本的地方）和從 x 2到 y 2價格為 0（此航班是免費的，因為您已經支付了使用 C 航班的預付費用）。
如果您在此修改后的圖中從節點 x 1開始運行 Dijkstra 演算法，您可以通過查看到達 y 1（不使用任何 C 航班）和 y 2（至少使用一次 C 飛行）。通過新圖表的路徑將告訴您要搭乘的航班。
這使輸入圖的大小加倍，這會稍微減慢 Dijkstra 演算法的速度，但不會漸近地影響運行時間。
uj5u.com熱心網友回復：
我認為您可以在每個節點的成本旁邊保留一個標志，表明您是否已經使用了C航班。此標志將決定下一次C飛行是否會花費您。
換句話說，C當您使用一條C邊時，不要將所有邊設定為零，而是將其保持在每個嘗試路徑的本地狀態。
您可以將設定標志的路徑優先于具有相同成本但未設定標志的其他路徑。這是一種啟發式方法，可幫助您的演算法更快地找到解決方案，但最終還是會這樣做。
現在，當你開始Dijkstra演算法，用路徑C包括成本會挺身而出優先級佇列中盡快的倍數A或B路徑在執法機關花費多達一C包括路徑C。從那里開始，據我所知，它只是一個標準的 Dijkstra。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/392074.html
下一篇：根據位置和值重復一個數字？