给定一组边和一个无向图，如何选择添加到图中的最佳边以最小化最短路径？

Question

我的想法是，对于我可以从中挑选的边集中的每条边，构建一个图的副本，并将该边插入其中，然后运行 Dijkstra。最好的边将来自最终总权重最低的图表。

但这似乎效率很低。我必须为集合中的每条边调用 Dijkstra。有更好的方法吗？

Answer 1

肮脏的伎俩：

在修改后的图表上运行 Djikstra。该图将包括原始图的所有顶点和边。两次。
对于每个顶点 i，创建一个顶点 i'。如果存在一条边 (u,v)，则创建一条边 (u',v')。 结果，我们有两个图表，除了 之外，看起来都一样。
现在魔术来了：

• 对于每个快捷方式 x, y 创建一条边 (x, y')。
• 合并目标和目标'

在该图上运行 Djikstra 将为您提供最短路径，包括快捷方式。为什么？

• 如果快捷方式由于某些原因没有帮助，我们将处于原始图表中，结果不会改变。
• 如果我们决定使用快捷方式，我们就会陷入“复制”图表中并且无法返回 - 因此我们只能使用一个快捷方式。由于目标是我们合并以来唯一的“单一”节点，因此我们仍然可以到达它。
因此，如果 Djikstra 在这个修改后的图中找到一条路径，我们就得到了新的最短路径，该路径将快捷方式纳入考虑范围。

最终的复杂性由 Djikstra 给出，并且由于我们只在混合中添加了 E + len(shortcuts) 边，因此与原始 Djikstra 相比，O 表示法没有任何改变。

Answer 2

例如，如果原始最佳路径是（s，u，v，w，x，y，z，t）。 我们可以不去吗(s,u,w',x',y',t)。这里我们使用两条新边 (u,w') 和 (yt)。