我有一个加权无向图 . 给定该图中两个顶点之间没有路径的顶点，我想在之间创建一条路径，方法是在图形中添加边，尽可能少地增加图的总权重 . 是否有已知的算法来确定要添加哪些边？
一个类似的问题是，如果我有一个国家的道路系统的图表，其中有两个城市无法通过道路彼此进入，我想 Build 最短的一组新道路将连接它们 . 在它们之间可能还有其他城市与两者都没有联系，如果它们存在，我想利用它们 .
这是一个小插图;红色和绿色是我想要连接的顶点，黑色线条是现有边缘，蓝色线条代表我想要存在的路径 .
是否有一种已知的算法可以提供该路径中缺少的边缘？
3 回答
对于缺失边缘，您可以使用权重为零的A *算法用于现有边缘和距离（或任何有意义的成本） .
https://en.wikipedia.org/wiki/A*_search_algorithm
实际上Dijkstra有一些预处理是最好的朋友 .
我回答了可能与此类似的问题：What is the time complexity if it needs to revisit visited nodes in BFS?
我所看到的共同点 - 您希望尽可能多地使用现有道路 . 你有时也需要打破它并 Build 新的道路 . 关键在于为现有的和“可能是新的”设置适当的权重 .
我的方法是什么 - 让我们说，每1公里的现有道路的成本为1.您可以对图表中所有现有道路求和，并说总共有1000公里 . 然后我会预处理整个图形，从每个节点（城市）我将创建到所有其他非直接连接城市的路径，每个城市每公里花费1000 1000，然后运行Dijkstra .
它将自动使用尽可能多的现有道路，并尽可能减少新道路 .
您也可以使用该设置来实现您想要的效果 .
想象一下，有两个城市距离彼此只有100米 . 而现有道路之间实际上有20 000公里的道路 . 根据我建议的设置，你将获得20000km的路径作为最好的路径（满足“如果没有必要，不 Build 任何新的道路”的需要） . 有时你真的想要这个 . 有时候你没有 . 如果你不这样做，你可以考虑“好吧，如果我建造一些额外的道路，它会大大降低距离，它仍然是更好的解决方案” . 如果是这种情况，您可以考虑降低新道路的价格（比如取消初始成本，或者每公里成本或两者兼而有之 - 取决于您采取的最佳产量） .
我不认为有一个公认的算法 . 但你可以尝试做以下事情 . 首先运行Vitterbi Triangulation，然后在这个完全连接的图上运行深度优先搜索 . 从A - > B中获取路径中新链接的总和 . 删除最长的新链接，然后重复 . 一旦无法到达A - > B的路径，请检查以前的解决方案，以查看哪些解决方案具有最小的新链接总和 .