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

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

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

A和E之间还有一条边，有两个重量，但我没能显示出来。
现在，首先我需要找到a和e之间的最短路径（因为我的应用程序，我必须这样做），即a-e-d-c，然后，用最小跨度连接所有图。有人能帮我提供一些线索吗对不起，英语不好，这不是我的母语

最佳答案

只是一个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，这是一个非常有趣的问题。
这可以通过运行kruskal的算法来解决。
源自Wikipedia：
创建一个forest F（一组树），其中图中的每个顶点都是一个单独的树，不包括最短路径中的顶点。
将最短路径作为一棵树添加到林中
创建一个集合，该集合包含图形中除最短路径中的边之外的所有边
而s不是空的，f还没有跨越
以最小重量从
如果该边连接两棵不同的树，则将其添加到林中，将两棵树合并为一棵树
否则丢弃该边

关于c++ - 最短路径和最小生成树的组合，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20729109/