考虑到边缘加权图的MST，如何找到从x到y的最小加权路径？

Question

我有一个由最小生成树表示的边缘加权无向图。每个顶点由一个整数表示。 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

Answer 1

在这种情况下，由于您得到了MST，因此您只知道图形中的总边缘权重很小。但是，MST中两个节点之间的路径并不能保证它是实际图形上这两个节点之间的最小路径。为了找到从节点x到节点y的最小加权路径，您可以在原始图（不是MST）上执行Dijkstra算法。 Dijkstra可以找到从起始节点（在本例中为x）到图中每个其他节点的最小距离。

执行Dijkstra算法，如下所示，并将信息存储在表中：

1. 从起始节点开始，在这种情况下，从x开始，然后转到权重最小的节点，从x

   ]

2. 从刚访问过的最低权重节点开始，探索邻居，然后再次选择权重最低的边缘

3. 从您要访问的边缘算起的总费用。如果您从x开始，然后访问a，然后访问c，则找到从x到a到c的总距离。

4. 如果节点的权重小于以前记录的权重，请更新表中的值，因为现在已找到较短的路径。

最终，执行此算法后，表格应包含从x到y的最低权重路径。

Answer 2

MST不一定包含从一个顶点x到另一个向量y的最短路径。最小生成树是为每个要访问的节点找到最小路径的树。这并不一定意味着MST中包括从x到y的最短路径。要找到从x到y的真正最短路径，您将必须运行算法以在原始图形上找到最短路径，例如Dijkstra的。