在两个顶点之间创建成本最低的路径
Create the lowest-cost path between two vertices
我有一个加权无向图。鉴于该图中的两个顶点之间没有路径，我想通过向图中添加边来创建它们之间的路径，尽可能少地增加图的总权重。是否有用于确定要添加哪些边的已知算法？
一个类似的问题是，如果我有一个国家/地区的道路系统图，其中有两个城市无法通过彼此的道路到达，并且我想建造最短的一组新道路来连接他们。它们之间可能还有其他城市与这两个城市都没有联系，如果它们存在我想利用它们。
这是一个小例子；红色和绿色是我要连接的顶点，黑线是存在的边，蓝线代表我要存在的路径。
是否有已知算法可以给出该路径中缺失的边？
我认为没有公认的算法。但是您可以尝试执行以下操作。首先 运行 维特比三角剖分，然后 运行 在这个全连接图上进行深度优先搜索。取A->B路径中新的link的总和，去掉最长的新的link，重复。一旦无法到达从 A -> B 的路径，请检查以前的解决方案以查看哪些解决方案具有最小的新 links.
您可以使用 A* 算法，现有边的权重为零，缺失边的距离（或任何有意义的成本）。
实际上，经过一些预处理的 Dijkstra 最适合您。
我回答的问题可能与此类似：
我看到的共同点 - 您希望尽可能多地使用现有道路。此外，有时您需要打破它并修建新道路。重点是为现有权重和 "possibly new ones".
设置适当的权重
我的方法是什么 - 假设现有道路每 1 公里的成本为 1。您可以将图表中所有现有道路相加，假设总共有 1000 公里。然后我会预处理整个图表，并从每个节点（城市）创建通往所有其他非直接连接城市的路径，每个城市每公里花费 1000 + 1000，然后 运行 Dijkstra 就可以了。
它会自动使用尽可能多的现有道路，并尽可能少地创建新道路。
您也可以稍微调整一下设置以达到您想要的效果。
想象一下，有两个城市相距仅 100m。它们之间实际上有一条从现有道路开始的路径，需要 20 000 公里。使用我建议的设置，您将获得 20000 公里的最佳路径（满足 "dont build any new roads if not necessary" 的需要）。有时你真的想要这个。有时你没有。如果你没有，你可以考虑"ok, if I build like a little of extra road and it dramatically lowers the distance, its still better solution"。如果是这种情况，您可以考虑降低新道路的价格（例如取消初始成本，或每公里成本或两者 - 这取决于您将什么作为最佳输出）。
我有一个加权无向图。鉴于该图中的两个顶点之间没有路径，我想通过向图中添加边来创建它们之间的路径，尽可能少地增加图的总权重。是否有用于确定要添加哪些边的已知算法？
一个类似的问题是，如果我有一个国家/地区的道路系统图，其中有两个城市无法通过彼此的道路到达，并且我想建造最短的一组新道路来连接他们。它们之间可能还有其他城市与这两个城市都没有联系，如果它们存在我想利用它们。
这是一个小例子；红色和绿色是我要连接的顶点，黑线是存在的边，蓝线代表我要存在的路径。
是否有已知算法可以给出该路径中缺失的边？
我认为没有公认的算法。但是您可以尝试执行以下操作。首先 运行 维特比三角剖分，然后 运行 在这个全连接图上进行深度优先搜索。取A->B路径中新的link的总和，去掉最长的新的link，重复。一旦无法到达从 A -> B 的路径，请检查以前的解决方案以查看哪些解决方案具有最小的新 links.
您可以使用 A* 算法，现有边的权重为零，缺失边的距离（或任何有意义的成本）。
实际上，经过一些预处理的 Dijkstra 最适合您。
我回答的问题可能与此类似：
我看到的共同点 - 您希望尽可能多地使用现有道路。此外，有时您需要打破它并修建新道路。重点是为现有权重和 "possibly new ones".
设置适当的权重我的方法是什么 - 假设现有道路每 1 公里的成本为 1。您可以将图表中所有现有道路相加，假设总共有 1000 公里。然后我会预处理整个图表，并从每个节点（城市）创建通往所有其他非直接连接城市的路径，每个城市每公里花费 1000 + 1000，然后 运行 Dijkstra 就可以了。
它会自动使用尽可能多的现有道路，并尽可能少地创建新道路。
您也可以稍微调整一下设置以达到您想要的效果。
想象一下，有两个城市相距仅 100m。它们之间实际上有一条从现有道路开始的路径，需要 20 000 公里。使用我建议的设置，您将获得 20000 公里的最佳路径（满足 "dont build any new roads if not necessary" 的需要）。有时你真的想要这个。有时你没有。如果你没有，你可以考虑"ok, if I build like a little of extra road and it dramatically lowers the distance, its still better solution"。如果是这种情况，您可以考虑降低新道路的价格（例如取消初始成本，或每公里成本或两者 - 这取决于您将什么作为最佳输出）。