我正在尝试通过在 MST 中添加新顶点来更新 MST。为此，我一直在关注 Chin 和 Houck 的“更新生成树”。 http://www.computingscience.nl/docs/vakken/al/WerkC/UpdatingSpanningTrees.pdf
论文中的一个步骤要求我在两个给定顶点之间的路径中找到最大的边。我的想法是找到顶点之间的所有可能路径，然后从路径中找到最大的边。我一直在尝试在 MATLAB 中实现这一点。然而，到目前为止，我一直没有成功。任何用于查找两个顶点之间的所有路径，甚至是两个给定节点/顶点之间路径中最大边的引导/清除算法都会受到欢迎。
作为参考，我想举一个例子。如果图形具有以下边 1-2、1-3、2-4 和 3-4，则 4 和 4 之间的路径为：
1) 4-2-1-3-4
2) 4-3-1-2-4
谢谢
该算法通过降低 t 值来从新的 MST 中排除大边缘。当算法完成时，t 将是为完成 MST 需要插入的最低边。
m 值表示从 r 到 z 的路径上的最大边，在每次 INSERT 运行时都是局部的。如果可能，在循环的每次迭代中降低 m，从而将先前的 m 边缘作为 t 的可能候选者移除。
用文字解释起来并不容易，我建议在纸上运行算法，直到步骤清楚为止。
我快速尝试在这里勾勒出这些步骤：http: //jacob.midtgaard-olesen.dk/ ?p=140
但基本上，该算法从旧 MST 中添加边，除非它在新节点 z 和旧 MST 中的另一个节点之间找到要添加的较小边。在示例中，边 (A,B) 不在新树中，因为算法找到了与 B 的更好连接。
请注意，在选择 h 和 k 时，如果 t 和 (w,r) 具有相等的边缘值，我相信您应该选择 (w,r)
最后，您可能应该通过算法的证明来了解算法为何有效。（我没有全部读完:)）