Dijkstra算法问题

如何将Dijkstra算法应用于图来找到MST，使得生成的树必须在两个给定顶点之间有一条边？（例如：MST必须包括X和Y之间的边缘）Dijkstra算法问题

感谢

2011-06-01 coder9

Dijkstra找不到MST。 – Waldheinz 2011-06-01 14:13:03

是的。它需要在这种情况下被修改 – coder9 2011-06-02 00:53:33

检查这[问题]（http://stackoverflow.com/questions/1909281/use-dijkstras-to-find-a-minimum-spanning-tree） – 2011-06-01 14:11:26

Dijkstra算法为最短路径（不MST），但类似于Dijkstra算法的东西，如修改，以找到一个最小生成树，是称为Prim算法。 Prim的算法保持一个增长的树，直到它横跨整个图。这里引入的额外约束并不会造成太大的困难：您只需从X-Y开始，作为您的树。

具体来说，假设你的MST必须包含边（X，Y）（如果有多个这样的边选择最小权重），那么从你的树开始，有两个节点X和Y以及它们之间的边。现在，在每一步选择最小边（u，v），其中u在树中，v在外部，将节点v和边（u，v）添加到树中，然后重复。

来源

2011-06-01 14:18:56 ShreevatsaR

+1为Prim的算法，非常有趣http://en.wikipedia.org/wiki/Prim%27s_algorithm – 2011-06-01 14:51:12

我可以在Prim's中简单地做到这一点，但问题是与使用Dijkstra找到MST与提到的限制 – coder9 2011-06-02 01:06:16

Dijkstra不会找到你一个MST。考虑三条边的简单图形，AB成本4，BC成本5和AC成本7. Dikjstra总是希望选择AB和AC作为AC的最短路径7，但总树权重为12.但是Prim的意志总是选择AB和BC，因为树的总重量是9，尽管从A到C的最短路径也是9.算法非常相似，但我永远不会调用与后来的Dijkstra相似的东西。如果这是一项家庭作业，也许教授只是想让你意识到Dijkstra是否容易进入Prim的算法？ – 2011-06-02 01:18:45

Dijkstra算法问题

回答

相关问题