最近接到這個任務
根據雙向道路系統，確定哪些城市值得在哪些城市之間修建道路，以便可以在不到 N 公里的時間內從任何城市到達任何其他城市。符合條件的道路的距離和建設成本單獨規定。最大限度地降低道路建設成本。
我從兩個矩陣制作了 java 圖形，用于可視化初始合格道路，但無法提出演算法，我對圖形不太熟悉）
uj5u.com熱心網友回復：
FOR EVER
M = 0
LOOP over every pair of cities
If min distance ( Dijkstra algorithm ) between cities > M
M = min distance
IF M <= N
BREAK
LOOP over eligible roads in order of increasing cost
IF road would reduce distance between two most distant cities
BUILD the road
請注意，Dijkstra 的許多實作都會給出從源到每個可能目的地的最小距離。這可用于優化回圈計算 M
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/495349.html