c++ - 生成具有负边权重且没有负循环的随机图

Question

负循环中的边权重之和为负。有了这个概念，有没有什么方法可以生成随机正负边权，并且没有负循环的图呢？这些图表对于测试 bellman_ford_shortest_paths 很有用。方法。

---

注:在this post他们使用 boost 库在没有这些条件的情况下生成图表。

Answer 1

我建议使用 generate_random_graph 来……生成一个随机图并修复任何负循环作为后处理步骤。

例如:

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/random.hpp>
#include <random>
#include <iostream>

using Graph = boost::adjacency_list<
    boost::vecS,
    boost::vecS,
    boost::directedS, 
    boost::no_property,
    boost::property<boost::edge_weight_t, double> >;

int main()
{
    std::mt19937 prng;
    Graph g;
    generate_random_graph(g, 100, 200, prng);

    // find cycles with negative sum and just add a large enough value to one
    // of the participating edges to make it postive
}