我有一组节点 AG、Z，定义了加权边缘，其中 AG 是漏斗中的各个节点，Z 在最底部。
可视化一个具有各种边缘的漏斗（V 形），但最终指向 Z，即最终节点，就像水流向单个点 Z。我们想要找到到达 Z 的最便宜的路径，它覆盖了漏斗中的所有节点。
以下是约束：
- 没有孤立节点（所有节点都已连接/包含）
- 我们希望最小化加权边的总和
- “共享边”，就像水向下流动时合并，只计算共享边的重量一次（换句话说，它可以自由地沿着潮湿的路径流动）
我应该使用哪种提升图算法来找到这个问题的最佳边集？
- ABDEZ 是覆盖很多节点的廉价路径
- CGZ 有点强迫，因为 G 只有一条通往 Z 的路径
- FZ 看起来很便宜，但后来我们注意到由于 CGZ 是强制的，所以 FGZ 实际上比 FZ 便宜（因为我们不需要重复计算 GZ 段，所以 FG 的增量成本只有 1）
所以，边的集合应该是 (AB, BD, DE, EZ, CG, FG, GZ)
我确信这不是一个新问题：我只是不知道足够的图论来识别/命名算法。
更新
在进一步研究该问题时，我发现如果该图不是有向的，则该问题会简化为最小生成树。换句话说，如果我们没有先验地指定 Z 是图中的最低点（通过使用箭头），并且允许水在两个方向上流动（通常是正确的，除非我们有阀门），那么第二个模型可以正常工作。
当然，我们现在可以选择新的 FZ 无向边来获得更小的权重，而不是被迫使用旧的 GZ有向边。
鉴于这些结果，如果我们确实需要对边缘进行定向，liori 的答案是对原始问题的最佳响应（即需要对算法进行编码）。
输出
D <--> E with weight of 1
F <--> G with weight of 1
A <--> B with weight of 2
E <--> Z with weight of 2
C <--> G with weight of 2
F <--> Z with weight of 2
B <--> D with weight of 3
Total Weight = 13
使用最小生成树的无向无环图代码
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/kruskal_min_spanning_tree.hpp>
#include <iostream>
int
main()
{
using namespace boost;
typedef adjacency_list < vecS, vecS, undirectedS,
no_property, property < edge_weight_t, int > > Graph;
typedef graph_traits < Graph >::edge_descriptor Edge;
typedef graph_traits < Graph >::vertex_descriptor Vertex;
typedef std::pair<int, int> E;
char letter[] = "ABCDEFGZ";
const int num_nodes = 8;
E edge_array[] = {
E(0,1), E(1,2), E(1,3), E(3,6), E(3,5), E(3,4), E(2,5), E(2,6),
E(5,7), E(5,6), E(6,7), E(4,7)
};
int weights[] = { 2, 6, 3, 5, 3, 1, 4, 2, 2, 1, 3, 2 };
std::size_t num_edges = sizeof(edge_array) / sizeof(E);
Graph g(edge_array, edge_array + num_edges, weights, num_nodes);
property_map < Graph, edge_weight_t >::type weight = get(edge_weight, g);
std::vector < Edge > spanning_tree;
kruskal_minimum_spanning_tree(g, std::back_inserter(spanning_tree));
int total_weight = 0;
for (std::vector < Edge >::iterator ei = spanning_tree.begin();
ei != spanning_tree.end(); ++ei)
{
std::cout << letter[source(*ei, g)] << " <--> " << letter[target(*ei, g)]
<< " with weight of " << weight[*ei]
<< std::endl;
total_weight += weight[*ei];
}
std::cout << "Total Weight = " << total_weight << std::endl;
return EXIT_SUCCESS;
}