给定一个边权重图的MST，如何找到从x到y的最小权重路径？
给定一个边权重图的MST，如何找到从x到y的最小权重路径？
提问于 2019-10-06 23:42:36
我有一个由最小生成树表示的边权重无向图。每个顶点都由一个整数表示。MST如下所示：
我想知道，如何使用这个MST来找到从顶点x到顶点y的最短路径？假设我想要找到从0到3的最短路径，很容易看到路径是0-2，2-3，总权重0.26+0.17 = 0.43。但是，我应该如何构建一种通用的方法来做到这一点呢？在伪代码中
edge weight
6-2 0,40
4-5 0.35
5-7 0.28
2-3 0.17
0-2 0.26
1-7 0.19
0-7 0.16回答 2
Stack Overflow用户
发布于 2020-03-09 02:26:51
在这种情况下，由于您获得了MST，因此您只知道图中的总边权重是最小的。但是，MST中两个节点之间的路径不能保证它是实际图上这两个节点之间的最小路径。为了找到从节点x到节点y的最小权重路径，您可以在原始图(而不是MST)上执行Dijkstra算法。Dijkstra可以找到从起始节点到图中每个其他节点的最小距离，在本例中为x。
按如下方式执行Dijkstra算法，并将信息存储在表中：
- 从起始节点(本例中为x)开始，从刚访问的权重最低的节点x
- 转到权重最小的节点，探索邻居并再次拾取权重最低的边
- 求和到目前为止您访问的边的总成本。如果您从x开始，然后访问a，然后访问c，则查找从x到a到c的总距离。
- 如果某个节点的权重低于之前记录的值，请更新表中的值，因为现在已经找到了一条更短的路径。
最终，在执行此算法后，该表应包含从x到y的最低权重路径。
Stack Overflow用户
发布于 2020-04-11 01:47:26
MST不一定包含从一个顶点x到另一个向量y的最短路径。最小生成树是找到每个要访问的节点的最小路径的树。这并不一定意味着从x到y的最短路径包含在MST中。要找到从x到y的真正最短路径，您必须运行一个算法来找到原始图形上的最短路径，就像Dijkstra的算法一样。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/58258835
复制相关文章
相似问题
腾讯云开发者
