图任务中最小道路费用的算法

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。