boost::successive_shortest_path_nonnegative_weights 的最小成本最大流量
Min-cost-max-flow with boost::successive_shortest_path_nonnegative_weights
我需要使用
计算流量网络的最小成本最大流量
boost::successive_shortest_path_nonnegative_weights()
BGL (v 1_60_0) 中可用的函数。
如 documentation、
中指定
the directed graph G=(V,E) that represents the network must be augmented to include the reverse edge for every edge in E. That is, the input graph should be Gin = (V,{E U ET}). [...] The CapacityEdgeMap argument cap must map each edge in E to a positive number, and each edge in ET to 0. The WeightMap has to map each edge from E to nonnegative number, and each edge from ET to -weight of its reversed edge.
我有一个简单的函数，对于添加到图中的每条边，添加一条具有上面指定的容量和权重的反向边：
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.
我做错了什么？
刚运行陷入同样的问题。经过几分钟的调试，我发现了问题。我使用 float 类型作为权重。因此，由于数值误差，修改后的边权重（负权重的 dijkstra 版本）可能会略低于 0。
可能的解决方案可能重写 "successive_shortest_path_nonnegative_weights.hpp" 以便它舍入小的负值
我需要使用
计算流量网络的最小成本最大流量boost::successive_shortest_path_nonnegative_weights()
BGL (v 1_60_0) 中可用的函数。 如 documentation、
中指定the directed graph G=(V,E) that represents the network must be augmented to include the reverse edge for every edge in E. That is, the input graph should be Gin = (V,{E U ET}). [...] The CapacityEdgeMap argument cap must map each edge in E to a positive number, and each edge in ET to 0. The WeightMap has to map each edge from E to nonnegative number, and each edge from ET to -weight of its reversed edge.
我有一个简单的函数，对于添加到图中的每条边，添加一条具有上面指定的容量和权重的反向边：
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.
我做错了什么？
刚运行陷入同样的问题。经过几分钟的调试，我发现了问题。我使用 float 类型作为权重。因此，由于数值误差，修改后的边权重（负权重的 dijkstra 版本）可能会略低于 0。 可能的解决方案可能重写 "successive_shortest_path_nonnegative_weights.hpp" 以便它舍入小的负值