给定一组边和一个无向图，我如何选择最佳边添加到图中以最小化最短路径？
Given a set of edges and an undirected graph, how do I pick the best edge to add to graph to minimize the shortest path?
我在想的是，对于我可以从中选择的边集中的每条边，构建一个图的副本，并将该边插入其中，然后 运行 Dijkstra 的。最好的边缘将来自最终总权重最低的图形。
但这似乎有点低效。我将不得不为集合中的每条边调用 Dijkstra。有更好的方法吗？
恶作剧：
运行 Djikstra 修改图。该图将包括原始图中的所有顶点和边。两次。
对于每个顶点 i，创建一个顶点 i'。如果有一条边 (u,v)，则创建一条边 (u',v')。
结果，我们有两张图除了 's.
外看起来都一样。
魔术来了：
- 对于每个快捷方式 x, y 创建一条边 (x, y')。
- 合并目标和目标'
运行在这张图上使用 Djikstra 会给你最短的路径，包括捷径。为什么？
- 如果由于某些原因快捷方式不起作用，我们将使用原始图表并且结果不会改变。
- 如果我们决定使用快捷方式，我们将陷入 copied 图中，无法返回 - 因此我们只能使用一个快捷方式。由于目标是我们合并后唯一的“奇异”节点，我们仍然可以到达它。
因此，如果 Djikstra 在这个修改后的图中找到一条路径，我们就有了将捷径纳入帐户的新的最短路径。
最终的复杂度由 Djikstra 给出，因为我们只添加了 E + len(shortcuts) 边到混合中，所以没有改变原始 Djikstra 的 O 符号。
我在想的是，对于我可以从中选择的边集中的每条边，构建一个图的副本，并将该边插入其中，然后 运行 Dijkstra 的。最好的边缘将来自最终总权重最低的图形。
但这似乎有点低效。我将不得不为集合中的每条边调用 Dijkstra。有更好的方法吗？
恶作剧：
运行 Djikstra 修改图。该图将包括原始图中的所有顶点和边。两次。
对于每个顶点 i，创建一个顶点 i'。如果有一条边 (u,v)，则创建一条边 (u',v')。
结果，我们有两张图除了 's.
外看起来都一样。
魔术来了：
- 对于每个快捷方式 x, y 创建一条边 (x, y')。
- 合并目标和目标'
运行在这张图上使用 Djikstra 会给你最短的路径，包括捷径。为什么？
- 如果由于某些原因快捷方式不起作用，我们将使用原始图表并且结果不会改变。
- 如果我们决定使用快捷方式，我们将陷入 copied 图中，无法返回 - 因此我们只能使用一个快捷方式。由于目标是我们合并后唯一的“奇异”节点，我们仍然可以到达它。
因此，如果 Djikstra 在这个修改后的图中找到一条路径，我们就有了将捷径纳入帐户的新的最短路径。
最终的复杂度由 Djikstra 给出，因为我们只添加了 E + len(shortcuts) 边到混合中，所以没有改变原始 Djikstra 的 O 符号。