最近在编码测试中，我遇到了一个基于图表的问题，我无法解决。
因此，在这个问题中，我们得到了一个道路网络(加权无向图)，道路由边表示(并且它们有一定的权重)，城市由顶点表示。此外，我们还获得了可以添加到给定道路网络中的拟议道路列表(即 3 个数字，其连接的 2 个端点/城市，其他数字是权重)。我们必须判断添加到网络中的哪条道路可以最小化网络中的总行驶距离。总行驶距离定义为所有城市对之间最短路径距离的总和。 约束:
没有。顶点数:100，边数:1000，道路建议数:1000。
解决这个问题最有效的方法是什么？
最佳答案
计算所有对的最短路径并将它们存储在矩阵中。 (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的长度。
假设 Floyd–Warshall，这一切都需要时间 O(|V|3 + k |V|2)，其中 k 是可以添加的边数。这肯定够快了 在给定的约束条件下。
关于algorithm - 改善图表中的总行驶距离，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/67148594/