要找到两个给定节点/顶点之间的最大路径

我想通过在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

谢谢

来源

2012-07-15 slowhead

该算法通过降低吨价，以排除新的MST大边缘。当算法完成时，t将成为插入完成MST的最低边缘。

m值代表从r到z的一条路径上的最大边缘，对INSERT的每次运行都是本地的。如果可能的话，m在循环的每次迭代处被降低，由此去除前一个m边作为t的可能候选。

用文字解释并不容易，我建议在纸上做一个算法运行，直到步骤清晰。

我做了一个快速的尝试勾画这里的步骤：http://jacob.midtgaard-olesen.dk/?p=140

但基本上，除非它找到一个较小的边缘到新节点Z和旧其他节点之间增加了算法增加了从旧MST边缘MST。在该示例中，边（A，B）不在新树中，因为算法找到了与B更好的连接。

注意，在选择H和K，如果T和（W，R）具有相同的优势价值，我相信你应该选择（W，R）

最后你应该走线槽的算法如下证明了解算法为什么起作用。（我没有看到这一切:)）

来源

2012-07-15 21:46:03

我删除了我的第一个答案，因为我对m的解释是错误的。我希望你找到有用的例子。如果您需要更多帮助，我可以稍后阅读证明。但正如我在其他答案中指出的，你不应该找到最大的边缘，算法本身就是这样做的。 – 2012-07-15 21:57:53

非常感谢Jacob Midtgaard-Olesen。我真的很感谢你的帮助 – slowhead 2012-07-16 07:02:13

如果我的答案足以让你的算法进行下去，你应该把答案标记为接受。 :) – 2012-07-16 16:24:18

要找到两个给定节点/顶点之间的最大路径

回答

相关问题