在两个顶点之间创建成本最低的路径
我有一个加权无向图。给定该图中的两个顶点之间没有路径，我想通过向图中添加边来创建它们之间的路径，尽可能少地增加图的总权重。是否有已知的算法来确定要添加哪些边？
一个类似的问题是，如果我有一个国家道路系统的图表，其中有两个城市彼此无法通过道路进入，我想修建一组最短的新道路来连接它们。它们之间可能有其他城市与两者都没有联系，如果它们存在，我想利用它们。
这里有一个小例子；红色和绿色是我要连接的顶点，黑色线是现有边，蓝色线表示我要存在的路径。
是否有已知的算法可以给出该路径中缺失的边缘？
共有3个答案
我认为没有公认的算法。但你可以试着做以下事情。首先运行Vitterbi三角剖分，然后在此完全连接的图上运行深度优先搜索。从-
实际上，经过一些预处理的Dijkstra对你来说是最好的朋友。
我回答了可能类似于这个问题的问题：如果需要重新访问BFS中的访问节点，则时间复杂度是多少？
我看到的共同点是——你想尽可能多地使用现有道路。此外，你有时需要打破这一点，修建新的道路。关键是为现有道路和“可能的新道路”设定适当的权重。
我的方法是什么——假设每1公里现有道路的成本为1。你可以在你的图表中求和所有现有道路，假设总共有1000公里。然后我将对整个图表进行预处理，从每个节点（城市）创建到所有其他没有直接连接的城市的路径，每个城市每公里的成本为1000 1000，然后在上面运行Dijkstra。
它将自动使用尽可能多的现有道路，并创建尽可能少的新道路。
此外，您还可以使用该设置来实现您想要的效果。
想象一下，有两个城市相距仅100米。实际上，它们之间有一条从现有道路到20000公里的道路。根据我建议的设置，您将获得20000公里的最佳路径（满足“如果没有必要，不要修建任何新道路”的需要）。有时候你真的想要这个。有时你不会。如果你不这样做，你可以考虑“好吧，如果我建一条额外的路，它会大大缩短距离，这是更好的解决方案”。如果是这种情况，你可以考虑降低新道路的价格（比如取消初始成本，或每公里成本，或两者兼而有之——这取决于你认为什么是最佳产出）。
可以对现有边使用权重为零的A*算法，对缺失边使用距离（或任何有意义的代价）。
https://en.wikipedia.org/wiki/A*_search\u算法
-
我正在尝试编写一个算法，该算法将重建Floyd-Warshall算法中所有顶点对之间的最短路径（如果有，则为最短路径绑定多条路径）。我从这个问题中得到了一些提示：https://stackoverflow.com/a/11371588/7447425 基于此，我修改了Floyd Warshall算法： 该图是边缘列表的形式，例如： 到目前为止，一切似乎都很顺利。 对于路径重建， 但这不管用。那么，
-
我试图通过在MST中添加新顶点来更新MST。为此，我一直在关注Chin和Houck的“更新生成树”。http://www.computingscience.nl/docs/vakken/al/WerkC/UpdatingSpanningTrees.pdf 论文中的一个步骤要求我在两个给定顶点之间的路径中找到最大的边。我的想法是找到顶点之间所有可能的路径，然后从这些路径中找到最大的边。我一直在尝试在
-
问题内容： 我正在使用networkx处理图。我有一个很大的图（其中有近200个节点），我尝试查找两个节点之间的所有可能路径。但是，据我了解，networkx只能找到最短的路径。如何不仅获得最短路径，还获得所有可能路径？ UPD：路径只能包含每个节点一次。 UPD2：我需要类似find_all_paths（）函数的功能，在此进行描述：python.org/doc/essays/graphs.htm
-
以下是练习： null null 我的算法正确吗？如果我做v到w，然后做w到v，这仍然被认为是线性时间吗？
-
枚举任意图中两个顶点之间的所有简单路径通常需要指数时间，因为顶点之间可能存在指数数量的简单路径。但是如果我们只对两个endpoint顶点之间至少一条简单路径上的顶点感兴趣呢？ 也就是说：给定一个无向图和两个不同的顶点，是否有多项式时间算法可以找到两个顶点之间至少一条简单路径上的每个顶点？这与连通性不同；不包括死胡同和死胡同。然而，分支和连接路径是允许的。 我发现编写一个看起来可以解决这个问题的算法
-
因此，如果我在一个图中有两个顶点，它们通过一个以上的边连接，而它们之间有相同的最短路径（即，如果我有节点a和节点B，它们直接通过三条边连接（它们之间有三条最短路径，每个距离为1)，所以计数应该返回3）我该如何修改BFS算法来实现这一点？这是我的代码，它只计算2个节点之间的最短路径，而不计算这些最短路径的个数。