在此图表任务中，最小化道路成本的算法

Question

来完成这项任务

最近，我根据双向道路的系统 ，确定值得在哪个城市之间建造道路，以便在不到n公里以下的任何城市到其他任何城市。合格道路的距离和建筑成本分别指定。最小化道路建设成本。

我从两个矩阵中制作了Java图，以可视化初始合格的道路，但无法提出算法，我并不真正熟悉图形）

Answer 1

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的许多实现都将使Minumim从源到每个可能的目的地的距离。这可以用于优化计算M的循环