改进图中的总行程距离

Question

最近在一次编码测试中，我遇到了一个基于图形的问题，我无法解决。

所以在这个问题中，我们得到了一个道路网络（一个加权无向图），道路由边表示（它们有一定的权重），城市由顶点表示。此外，我们还获得了一份可添加到给定道路网络中的拟建道路列表（即3个编号、2个endpoint/连接的城市，其他编号为权重）。我们必须知道，在加入网络后，哪条道路使网络中的总行驶距离最小化。总出行距离定义为所有城市对之间的最短路径距离之和。约束条件：

顶点数：100，边数：1000，道路建议数：1000。

解决这个问题最有效的方法是什么？

Answer 1

计算所有对的最短路径并将它们存储在矩阵中。（Floyd–Warshall很简单，可以很好地处理密集图；也可以从每个顶点运行Dijkstra。）

对于可以添加的每个边uv，我们可以将s和t之间的更新距离评估为min（d（s， t）， d（s， u）（uv）d（v， t）， d（s， v）（uv）d（u， t）），其中d表示基图中的距离，（uv）是uv的长度。

假设弗洛伊德-沃沙尔，这都需要时间O（|V|³k|V|²），其中k是可以添加的边数。在给定的约束下，这肯定足够快了。