贝尔曼-福德算法 C++ 实现

Question

我正在实现 Bellman Ford 算法，其中输入是一个有向加权图，输出要么是 1（存在负环），要么是 0（没有负环）。

我理解 Bellman Ford 算法，并已经在许多测试用例上运行了以下代码，但似乎无法通过我想要提交的平台上的所有测试用例。我无法看到代码失败的特定测试用例。

任何提示可能出错的地方都将非常有帮助

约束条件

1 ≤ n ≤ 10^3，0 ≤ m ≤ 10^4，边权重为绝对值最多为 10^3 的整数。 (n = 顶点数, m = 边数)

代码

#include <iostream>
#include <limits>
#include <vector>

using std::cout;
using std::vector;

int negative_cycle(vector<vector<int>> &adj, vector<vector<int>> &cost) {
  vector<int> dist(adj.size(), std::numeric_limits<int>::max());
  dist[0] = 0;
  for (int i = 0; i < adj.size() - 1; i++) {
    for (int j = 0; j < adj.size(); j++) {
      for (int k = 0; k < adj[j].size(); k++) {
        if (dist[j] != std::numeric_limits<int>::max()) {
          if ((dist[adj[j][k]] > dist[j] + cost[j][k])) {
            dist[adj[j][k]] = dist[j] + cost[j][k];
          }
        }
      }
    }
  }
  for (int j = 0; j < adj.size(); j++) {
    for (int k = 0; k < adj[j].size(); k++) {
      if (dist[j] != std::numeric_limits<int>::max()) {
        if ((dist[adj[j][k]] > dist[j] + cost[j][k])) {
          return 1;  // negative cycle
        }
      }
    }
  }
  return 0;  // no negative cycle
}

int main() {
  int n, m;
  std::cin >> n >> m;
  vector<vector<int>> adj(n, vector<int>());
  vector<vector<int>> cost(n, vector<int>());
  for (int i = 0; i < m; i++) {
    int x, y, w;
    std::cin >> x >> y >> w;
    adj[x - 1].push_back(y - 1);
    cost[x - 1].push_back(w);
  }
  std::cout << negative_cycle(adj, cost);
}

- user8147810

---

请花些时间刷新帮助页面，参观SO之旅，特别是关于如何提出好问题，以及此问题清单。最后，请学习如何调试程序。 - Some programmer dude

节点数、边数和最大绝对权重值的限制是什么？ - Photon

@Photon添加了约束！ - user8147810

我会手动运行一次失败的程序，并将其与调试值进行比较。 - One Man Monkey Squad

@Someprogrammerdude的挫败感促使我写下这个问题，但我完全理解。我已经查看了您提供的链接，并会确保从现在开始遵守规则。谢谢 :) （我应该删除这个问题吗？） - user8147810

Answer 1

vector<int> dist(adj.size(), std::numeric_limits<int>::max());
dist[0] = 0;

在这些行中，您将顶点#0标记为起点，而所有其他顶点都标记为不可达。问题在于，如果您的图分成了两个以上不同的部分，则它不会找到不包含顶点#0的部分的负循环，因为来自另一部分的顶点仍然是不可达的。

解决方案：将所有初始距离设为零。

- Daniel Z.