# Calculating distances between nodes in graph with negative cycles

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.

• 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. – Phrancis Apr 13 '17 at 8:36
• I thought this could be posted here since it compiles and is working (except possibly for overflow case). In any case, noted. – mcansado Apr 13 '17 at 9:01
• @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/… – BCdotWEB Apr 13 '17 at 12:11
• This is perfectly reviewable code. Errors like stack overflow are usually solved by using better techniques (which is exactly what code review is about). – Martin York Apr 13 '17 at 16:35
• I voted to reopen the question, we just need a few more votes and we should be good to go. – Phrancis Apr 13 '17 at 21:02