令 G=(V,E) 為有向圖。讓 V 中的 s 是一個頂點。令 V 中的 k 是某個頂點，使得 k≠s。給定路徑 p，將其成本定義為 p 中的邊數。然而，如果一條路徑通過頂點 k，那么在頂點 k 被訪問之后使用的每條邊都計為 5。
對于 V 中的每個 v，用 c(s,v) 表示從 s 到 v 的最便宜路徑的成本。建議一種有效的演算法來計算 V 中的每個 v 的值 c(s,v)。
我也不能使用 Dijkstra 演算法。
我最初的想法是使用單源最短路徑演算法。
這是我的嘗試：
演算法：
- 使用 BFS 計算從 s 到 v 的所有路徑（未加權），將路徑存盤在串列中。
- 遍歷串列中的每條路徑，如果 k 在路徑中，則計算 k 之后的節點數（將其分配給變數 num），并將 4*num 添加到步驟 1 中已經計算的總和。
- 選擇具有最小結果數的路徑，并回傳它。
我想我可以做得比這更好，因為在最壞的情況下，我們將有 |V|/2 條路徑，所以時間復雜度可以是 O(n^2)。
我想聽聽一些改進任務的建議。
非常感謝！
uj5u.com熱心網友回復：
只能有 2 種型別的路徑 - 通過 k 的路徑和不通過的路徑：
s --> ... --> vs --> ... --> k --> ... --> v
現在要找到第一類路徑，我們可以簡單地從s具有特殊條件的節點執行 BFS - 如果我們碰巧到達節點，我們將永遠無法去任何地方k
對于其他路徑，我們可以將它們分成 2 部分，s --> ... --> k并且請k --> v注意，第一個 BFS 已經知道第一部分。現在我們可以再次執行 BFS，這次是從 node 開始k。
現在s --> v任何人的最短路徑v只是min(type1PathCost[v], type1PathCost[k] type2PathCost[v] * 5)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/350531.html
上一篇：兩個騎士相遇的最少步數