c++ - 带boost::successive_shortest_path_nonnegative_weights的最小成本-最大流量

我需要使用

boost::successive_shortest_path_nonnegative_weights()

BGL(v 1_60_0)中可用的功能。
如documentation中所指定，



我有一个简单的函数，对于添加到图形中的每个边缘，添加一个具有如上所述容量和重量的反向边缘:

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.

我究竟做错了什么？

最佳答案

只是遇到了同样的问题。经过几分钟的调试，我发现了问题。我使用浮点类型的重量。因此，修改后的边缘权重(负权重的dijkstra版本)可能会因数值误差而变得略低于0。
可能的解决方案可能是重写“successive_shortest_path_nonnegative_weights.hpp”，以便将较小的负值取整

关于c++ - 带boost::successive_shortest_path_nonnegative_weights的最小成本-最大流量，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/35746487/