我有一组节点A-G、Z，定义了加权边，其中A-G是漏斗中的各种节点，Z在最底部。将漏斗（V形）可视化，具有各种边缘，但最终指向Z，即水流向单个点Z。我们希望找到最便宜的路径到达Z，该路径覆盖了漏斗中的所有节点。
以下是约束条件：
- 没有孤立节点（所有节点都连接/包含） - 我们希望最小化加权边的总和 - “共享边缘”（如水向下流动时合并），仅计算共享边缘的权重一次（换句话说，沿着湿润的路径自由向下流动）
应使用哪个增强图算法来查找此问题的最佳边集？
使用最小生成树的无向无环图代码
以下是约束条件：
- 没有孤立节点（所有节点都连接/包含） - 我们希望最小化加权边的总和 - “共享边缘”（如水向下流动时合并），仅计算共享边缘的权重一次（换句话说，沿着湿润的路径自由向下流动）
应使用哪个增强图算法来查找此问题的最佳边集？
- A-B-D-E-Z是一条涵盖许多节点的廉价路径
- C-G-Z有点强制，因为G只有一条通往Z的路径
- F-Z看起来很便宜，但是我们注意到由于C-G-Z是强制性的，所以F-G-Z实际上比F-Z更便宜（因为我们不需要双重计算G-Z段，F-G的增量成本仅为1）
因此，边集应为（A-B、B-D、D-E、E-Z、C-G、F-G、G-Z）
我确定这不是一个新问题：我只是不了解足够的图论来识别/命名算法。
更新
在进一步研究问题时，我发现如果图形不是有向的，那么问题就简化为最小生成树。换句话说，如果我们没有事先指定 Z 是图中最低点（通过箭头使用），并且允许水在两个方向上流动（通常是真实的，除非我们有阀门），那么这个第二个模型将工作得很好。
当然，我们现在可以选择较小权重的新F-Z无向边，而不是被迫使用旧的G-Z有向边。
考虑到这些结果，如果我们确实需要边是有向的，liori's answer 是对原问题（即需要编写算法）的最佳回应。
输出
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;
}