SPFA 松弛次数的蒙特卡洛试验

熟知 SPFA 算法在随机图上表现较优．考虑到实际分析极其复杂，我们通过蒙特卡洛模拟来验证这一结论．

首先给出 SPFA 算法的 C++ 实现：

SPFA 实现

using Edge = pair<size_t, int64_t>;
using Graph = vector<vector<Edge>>;

size_t spfa_test(const Graph &graph, size_t source) {
  static constexpr int64_t INF = numeric_limits<int64_t>::max() >> 2;
  size_t V = graph.size();
  queue<size_t> q;
  vector<size_t> count(V, 0);
  vector<int64_t> dist(V, INF);
  vector<bool> in_queue(V, false);
  q.push(source), in_queue[source] = true, dist[source] = 0;

  size_t relaxations = 0;
  while (!q.empty()) {
    size_t u = q.front();
    q.pop(), in_queue[u] = false;
    for (const auto &[v, w] : graph[u]) {
      ++relaxations;
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        count[v] = count[u] + 1;
        if (count[v] >= V)
          return relaxations; // Negative cycle detected
        if (!in_queue[v])
          q.push(v), in_queue[v] = true;
      }
    }
  }

  return relaxations;
}

Trial 1

本次试验的生成图的算法如下：

随机图生成

Graph random_graph(size_t V, size_t E, int64_t min_weight, int64_t max_weight) {
  Graph graph(V);
  static mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  uniform_int_distribution<size_t> dist_node(0, V - 1);
  uniform_int_distribution<int64_t> dist_weight(min_weight, max_weight);
  for (size_t i = 0; i < E; ++i) {
    size_t u = dist_node(rng);
    size_t v = dist_node(rng);
    int64_t w = dist_weight(rng);
    graph[u].emplace_back(v, w);
  }
  return graph;
}