Какой алгоритм буст-графа я использую?

У меня есть набор узлов 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 является самой низкой точкой на графике (с помощью стрелок), и воде было разрешено течь в обоих направлениях (как правило, верно, если у нас нет клапанов), то эта вторая модель будет работать нормально.

Конечно, вместо того, чтобы быть вынужденным использовать старый направленный край G-Z, Теперь мы можем выбрать новый F-Z ненаправленный край для меньшего веса.

В свете этих результатов, если мы действительно хотим, чтобы края были направленный, ответ Лиори является лучшим ответом на исходный вопрос (т. е. алгоритм должен быть закодирован).

Выход

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;
}