给定边加权图的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不一定包含从一个顶点x到另一个向量y的最短路径。最小生成树是为要访问的每个节点找到最小路径的树。这并不一定意味着从x到y的最短路径包含在MST中。要找到从x到y的真正最短路径，您必须运行一个算法来找到原始图上的最短路径，就像Dijkstra的一样。

Answer 2

在这种情况下，由于给了你一个MST，你只知道图中的总边权重是最小的。然而，MST中两个节点之间的路径并不保证它是实际图上这两个节点之间的最小路径。为了找到从节点x到节点y的最小加权路径，可以对原始图(不是MST)执行Dijkstra算法。Dijkstra可以找到从一个起始节点(在本例中为x)到图中所有其他节点的最小距离。

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

>

从起始节点（在本例中为 x）开始，然后转到 x 中权重最小的节点

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

从你正在访问的边缘算出总成本。如果你从x开始，然后访问a，然后访问c，找到从x到a到c的总距离。

如果节点的权重低于之前记录的值，请更新表中的值，因为现在找到了更短的路径。

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