我需要使用
boost::successive_shortest_path_nonnegative_weights()
BGL (v 1_60_0) 中可用的功能。如文档中所述,
表示网络的有向图 G=(V,E) 必须扩充为包含 E 中每条边的反向边。也就是说,输入图应该是 Gin = (V,{EU ET})。[...]CapacityEdgeMap 参数 cap 必须将 E 中的每条边映射到一个正数,并将 ET 中的每条边映射到 0。WeightMap 必须将每条边从 E 映射到非负数,并将每条边从 ET 映射到 -weight of它的反向边缘。
我有一个简单的函数,对于添加到图中的每条边,添加一条具有上述容量和权重的反向边:
void add_edge_and_reverse(vertex_desc& source, vertex_desc& target, Edge& edge, flow_network_t& fn, boost::associative_property_map<std::map<edge_desc, edge_desc>>& rev_map)
{
std::pair<edge_desc, bool> e = boost::add_edge(source, target, edge, fn);
Edge reverse_edge(-edge.cost, 0);
std::pair<edge_desc, bool> e_rev = boost::add_edge(target, source, reverse_edge, fn);
rev_map[e.first] = e_rev.first;
rev_map[e_rev.first] = e.first;
}
现在,该图包含反向边,并且它们具有负权重,这与我正在使用的算法的名称形成鲜明对比。结果,当我执行算法时,我得到了这个错误:
ValueError: The graph may not contain an edge with negative weight.
我究竟做错了什么?