CODEWITHSUNDEEP
c++algorithmstl
user8147810
user8147810

Reputation:

Bellman Ford implementation C++

I'm implementing the Bellman Ford algorithm wherein the input is a directed weighted graph and the output is either a 1 (there is a negative cycle) or a 0 (no negative cycle).

I understand the Bellman Ford algorithm and have run the following code on quite a lot of test cases but can't seem to pass all the test cases on the platform where I wish to submit. I can't see the particular test case where the code is failing.

Any pointers as to where the problem might lie would be extremely helpful

Constraints

1 ≤ n ≤ 10^3 , 0 ≤ m ≤ 10^4 , edge weights are integers of absolute value at most 10^3 . (n = vertices, m = edges)

Code

#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);
}

Upvotes: 3

Views: 370

Answers (1)

Daniel Z.
Daniel Z.

Reputation: 389

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

In this lines you mark vertex #0 as starting point, while all other you mark as unreachable. The problem is that if your graph is divided into >=2 distinct parts, it won't find a negative cycle for part that doesn't contain vertex #0, because vertices from other part would still be unreachable.

Solution: set all initial distances to zero.

Upvotes: 3

Related Questions