c++ - 最短路径与最小生成树的结合

Question

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

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

A 和 E 之间也有一条边，权重为 2，但我无法显示。

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

Answer 1

只是一个 MST

如果您只需要 MST，这只需要运行 Kruskal's algorithm (见下文)或 Prim's algorithm :

1. Initialize a tree with a single vertex, chosen arbitrarily from the graph.
2. Grow the tree by one edge: Of the edges that connect the tree to vertices not yet in the tree, find the minimum-weight edge, and transfer it to the tree.
3. Repeat step 2 (until all vertices are in the tree).

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

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

A 和 E 之间的最短路径是 2(直接从 A 到 E)，但 MST (A-B-C-D-E) 不包括该边。

‘MST’包括一些最短路径

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

这可以通过运行具有较小变化的 Kruskal 算法来解决。

源自 Wikipedia :

• 创建一个森林 F(一组树)，其中图中的每个顶点都是一棵单独的树，不包括最短路径中的顶点。
• 将最短路径作为一棵树添加到森林
• 创建一个包含图中所有边的集合S，不包括来自最短路径的边
• 当 S 非空且 F 尚未跨越时
  • 从S中移除一条权重最小的边
  • 如果该边连接两棵不同的树，则将其添加到森林中，将两棵树合并为一棵树
  • 否则丢弃该边