我試圖根據這個解決方案撰寫偽代碼。但我無法理解這部分“一旦我們運行了 Bellman-Ford，我們就可以回顧 Floyd-Warshall 的結果，以確定哪些部分路徑對應于 G' 中找到的路徑”。任何人都可以使用偽代碼幫助我理解這一點嗎？
uj5u.com熱心網友回復：
讓我們看一個非常簡單的例子，一個加油站。
求 G' 中的最短路徑是start - s - target
要在 G 中找到對應的路徑，查看 G' 路徑中的每一跳，并找到 G 中 G1 跳中節點之間的最短可行路徑
start - s 變成start - v1 - s
s - 目標變成s - v2 - target
將部分路徑加在一起我們得到了答案
start - v1 - s - v2 - target
所以偽代碼是
Construct G'
Find P' the shortest path in G'
LOOP over hops in P'
Find Pg shortest path between hop source and hop destination in G
Add Pg to Ps ( eliminating common vertex )
Output Ps
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/514853.html
上一篇：std::max_element(vList.begin(),vList.end())回傳的迭代器在清除和更新向量(vList)后更改值