6

我需要使用

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.

我究竟做错了什么？

4

1 回答 1

0

刚刚遇到了同样的问题。经过几分钟的调试，我发现了问题。我使用浮点类型作为权重。因此，修改后的边权重（用于负权重的 dijkstra 版本）可能会因数值误差而略低于 0。可能的解决方案可能是重写“successive_shortest_path_nonnegative_weights.hpp”，以便它舍入小的负值

于 2016-12-06T21:18:07.213 回答