最短路径和最小生成树的组合

我试过做无向加权图的最小生成树。但是，我需要找到一对或多对节点之间的最短路径。之后，我必须找到图的最小生成树。我已经找到了必要节点之间的最短路径，但我不知道如何找到包含这些最短路径的最小生成树。让我举个例子。最短路径和最小生成树的组合

G 
|2 
H  A 
|1  |6  
F  ------B 
|1   | 7 
E -----D-----C 
    2  8

A和E之间还有一个边，有2个重量但我无法显示它。

现在，首先我需要找到A和E之间的最短路径（我必须这样做是因为我的应用程序），它是A-E-D-C，然后用最小跨度连接所有图形。有没有人帮助我提供一些线索？对不起，我英语不好它不是我的母语

来源

2013-12-22 caesar

与论坛网站不同，我们不使用“谢谢”或“任何帮助表示赞赏”，或在[so]上签名。请参见“[应‘你好’，‘谢谢’标语，并称呼从撤职？]（http://meta.stackexchange.com/questions/2950/should-hi-thanks-taglines-and-salutations-be -removed - 从 - 个）。 –

只是一个MST

如果你只是想在MST，这只是涉及到运行Kruskal's algorithm（见下文）或Prim's algorithm：

初始化一个单一顶点的树，从图中任意选择。

将树扩大一个边：在将树连接到树中尚未存在的顶点的边中，找到最小权重边，并将其转移到树中。

重复步骤2（直到所有顶点都在树中）。

这并不涉及获取顶点之间的最短路径。事实上，它不一定包含一些最短的路径。考虑：

A 
1 |\ 
    B \ 
1 | \ 2 
    C \ 
1 | \ 
    D-----E 
    1

A和E之间的最短路径是2（只是从A至E直接地），但MST（A-B-C-d-E）不包括边缘。

“MST”包括一些最短路径

如果你想找到MST包括一些最短路径，这是一个最有趣的问题。

这可以通过运行克鲁斯卡尔算法的一个小变化来解决。

从Wikipedia衍生：

创建林F（一组的树木），其中图中的每个顶点是一个单独的树，不包括从最短路径的顶点。
为一棵树添加的最短路径森林
创建一个包含所有在图中不包括的最短路径边缘上的边缘的集合S
虽然S是为非空和F还没有跨越
- 选自S
- 删除以最小的重量的边缘如果边连接两个不同的树，然后将其添加到森林里，两棵树合并为一棵树
- 否则丢弃边缘

来源

2013-12-22 12:00:52 Dukeling

最短路径和最小生成树的组合

回答

相关问题