1
\$\begingroup\$

Full disclosure: this is for an online course.

The code calculates the distances between a starting node in a graph and all other nodes using the Bellman-Ford algorithm. The graph may contain negative cycles: in that case, the output should represent that distance with '-'. If there is no link between the starting node and another node it should '*'. Else, it should output the distance.

The code is working but I believe there is an overflow issue which I don't know how to solve. The constraints specify the following max values:

  • Nodes: 10^3;
  • Edges: 10^4;
  • Egde weights: 10^9

Testing for all logic-related corner cases led to no issues, everything was working correctly. The test this is failing is (most probably) related to overflow.

The code

void bfs(vector<vector<int> > &adj, queue<int> q, vector<bool> &shortest) {
  int size = adj.size();
  vector<bool> visited(size, false);
  while (!q.empty()) {
    int v = q.front();
    if (visited[v]) {
      q.pop();
    } else {
      q.pop();
      for (int i = 0; i < adj[v].size(); i++) {
        shortest[adj[v][i]] = true;
        q.push(adj[v][i]);
      }
    }
    visited[v] = true;
  }
}

void shortest_paths(vector<vector<int> > &adj, vector<vector<int> > &cost, int s, 
  vector<double> &distance, vector<bool> &reachable, vector<bool> &shortest) {
  int size = adj.size();
  distance[s] = 0;
  reachable[s] = true;
  queue<int> negative_cycle;
  // Set initial distances and get negative cycles
  for (int i = 0; i <= size; i++) {
    for (int j = 0; j < size; j++) {
      for (int k = 0; k < adj[j].size(); k++) {
        // Edge relaxation
        if (distance[adj[j][k]] > distance[j] + cost[j][k]) {
          reachable[adj[j][k]] = true;
          if (i == size) {
            // Store negative cycles
            negative_cycle.push(adj[j][k]);
            shortest[adj[j][k]] = true;
          }
          distance[adj[j][k]] = distance[j] + cost[j][k];
        }
      }
    }
  }
  bfs(adj, negative_cycle, shortest);
}

and the main is

int main() {
  int n, m, s;
  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++) {
    double x, y, w;
    std::cin >> x >> y >> w;
    adj[x - 1].push_back(y - 1);
    cost[x - 1].push_back(w);
  }
  std::cin >> s;
  s--;
  vector<double> distance(n, std::numeric_limits<double>::infinity());
  vector<bool> reachable(n, false);
  vector<bool> shortest(n, false);
  shortest_paths(adj, cost, s, distance, reachable, shortest);
  for (int i = 0; i < n; i++) {
    if (!reachable[i]) {
      std::cout << "*\n";
    } else if (shortest[i]) {
      std::cout << "-\n";
    } else {
      std::cout << distance[i] << "\n";
    }
  }
}

I'm using double and infinity since that is needed for the algorithm (you can read about it here). From the googling I've done, I get this shouldn't overflow since the max possible distance would be 10^4 * 10^9 = 10^13 which is still within double's span. I don't have much experience using infinity or doubles like this, and from what I've researched I couldn't trace the problem.

\$\endgroup\$
  • \$\begingroup\$ On this site we review only working code. If you can narrow down which case(s) is/are causing overflow, I feel sure Stack Overflow can help with the specific problem. \$\endgroup\$ – Phrancis Apr 13 '17 at 8:36
  • \$\begingroup\$ I thought this could be posted here since it compiles and is working (except possibly for overflow case). In any case, noted. \$\endgroup\$ – mcansado Apr 13 '17 at 9:01
  • \$\begingroup\$ @mcansado These kind of questions are on the border. Considering that you want us to fix your issue, I fear that's what makes this off-topic. See: codereview.meta.stackexchange.com/questions/6957/… \$\endgroup\$ – BCdotWEB Apr 13 '17 at 12:11
  • \$\begingroup\$ This is perfectly reviewable code. Errors like stack overflow are usually solved by using better techniques (which is exactly what code review is about). \$\endgroup\$ – Martin York Apr 13 '17 at 16:35
  • \$\begingroup\$ I voted to reopen the question, we just need a few more votes and we should be good to go. \$\endgroup\$ – Phrancis Apr 13 '17 at 21:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.