4
Следующий код выдает «отрицательный вес края» на prim_minimum_spanning_tree, даже если я использую только положительных чисел. Что нужно изменить, чтобы заставить его работать?Неожиданная отрицательная ошибка веса края в boost :: prim_minimum_spanning_tree
typedef boost::property<vertex_distance_t, int> VertexProperty;
typedef boost::property<edge_weight_t, int> EdgeProperty;
typedef adjacency_list<vecS, vecS, undirectedS, VertexProperty, EdgeProperty> Graph;
typedef pair<int, int> Edge;
Edge edges[] = {Edge(0, 1), Edge(1, 2)};
int weights[] = {2, 1}; // this works: int weights[] = {1, 2};
Graph g(edges, edges + sizeof(edges)/sizeof(Edge), weights, 3);
std::vector<Graph::vertex_descriptor> predecessors(num_vertices(g));
boost::prim_minimum_spanning_tree(g, &predecessors[0]);
Примечание: Я могу добиться успеха, изменив значения веса.
Компилятор: MS Visual Studio 2010 C++ версии подталкивания: 1,54
Это не похоже, что они были бы, но, возможно, весы кумулятивны, поэтому любой спуск в весе означает, что край имеет отрицательный вес? Очевидный тест: всегда ли это происходит, если веса возрастают и всегда терпят неудачу, если они снижаются? –
@ Джерри Коффин: Да, он чувствителен к заказу. Поскольку приведенный выше код работает правильно с boost ver 1.53, я склонен считать, что это ошибка в последней версии boost (1.54). – alexm
@alexm Я вижу, что вы уже [сообщили об ошибке] (https://svn.boost.org/trac/boost/ticket/9012), и он исправлен (невероятно быстро!). – llonesmiz