給定的是一個有向圖 G = (V, E)，邊權重為 w:E 到 R 。
該圖表示布魯克林的道路，每條邊上的權重表示道路的長度（以英里為單位）。獎品放置在節點 t（在 V 中）。給定的是 V 中的一組節點 A（A 是 V 的子集），以及一個函式 s:A 到 R 。
在 A 中的每個 v 中都有一個玩家。在游戲開始時，所有玩家同時離開并朝著獎品前進。
每個玩家從其原點到 t 的最短路徑中前進。從節點 v 出發的玩家以恒定速度 s(v) 前進，即對于 E 中的每個 e，該玩家需要 w(e)/s(v) 個時間單位才能穿過道路 e。
提出一種回傳獲勝者的有效演算法。
我的嘗試：
演算法：
- 在 A 中的某個節點 v 上運行 Dijkstra，并啟動一個大小為 |A| 的陣列 （對于每個玩家）。
- 對于 A 中的每個 v，遍歷從 v 到 t 的最短路徑，并在每次迭代中將 w(e)/s(v) 添加到陣列中該特定節點的總和。
- 回傳陣列的最小值。
我認為這可以改進，例如用其他資料結構替換陣列，這將使最后一步更有效率，但我不知道如何。
我將不勝感激任何幫助！
謝謝！
uj5u.com熱心網友回復：
您可以通過從目標節點運行一次 Dijkstra 演算法t來計算所有到達/來自 的最短路徑來完成此操作t。您正在尋找 的最小值，總而言之a ∈ A，Distance(a, t) / Speed(a)其中距離是來自 Dijkstra 演算法的標準邊權重總和。由于原始圖是有向圖，因此您需要先反轉所有邊的方向并處理該圖。
如果“A”很小，您可以通過在訪問 中的所有節點后立即停止 Dijkstra 演算法來稍微優化它A，盡管最壞情況的運行時間是相同的。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/360325.html
上一篇：我的MapsActivity崩潰了，沒有任何錯誤訊息
下一篇：隨著用戶活動的增加，查詢變慢