Bellman Ford Algorithm failing at an unknown test case

Question

I am working on a problem set for one of the past courses. I am supposed to implement Bellman Ford Algorithm such that from a source s, I have to find the following:

1. If the node is unreachable from s (Output as *)
2. If the node is reachable but is a part of a negative cycle and therefore, there is no shortest path (output as -)
3. Otherwise, output shortest path from s to the node

I have written the following code which fails at an unknown test case. Can someone help me debug it?

void relax_edges(vector <vector<int>> &adj, 
                 vector <vector<int>> &cost, 
                 vector<long long> &dis) 
  {
  /*Takes input as adjacency list and relax all possible edges
  */

  for (int i = 0; i < adj.size(); i++) {
    for (int j = 0; j < adj[i].size(); j++) {
      if (dis[i] < std::numeric_limits < long long > ::max() 
             && dis[adj[i][j]] > dis[i] + cost[i][j]){
        //std::cout<< adj[i][j]<<" "<<i<<"\n";
        dis[adj[i][j]] = dis[i] + cost[i][j];
      }
    }
  }
}

void bfs(vector<vector<int> > &adj, vector<int>& shortest, int s){
    vector<int> seen (adj.size(), 0);
    //seen[s] = 1;
    queue<int> q;
    q.push(s);
    int t;
    while(!q.empty()){
        t = q.front();
        q.pop();
        if (seen[t] == 3)
            break;
        seen[t]+=1;
        for(int i=0;i<adj[t].size();i++){
            q.push(adj[t][i]);
        }
    }

    for(int i=0;i<seen.size();i++)
        if(seen[i]>=1)
            shortest[i] = 0;
}

void shortest_paths(vector <vector<int>> &adj,
                    vector <vector<int>> &cost,
                    int s,
                    vector<long long> &dis,
                    vector<int> &reachable,
                    vector<int> &shortest) {

  dis[s] = 0;// distance of s is 0 from s      
  int result;
  for (int i = 0; i < adj.size() - 1; i++) { //Running Bellman Ford |V-1| times
    relax_edges(adj, cost, dis);
  }
  vector<long long> distance2(dis.size(), 0);
  for (int i = 0; i < distance2.size(); i++)
    distance2[i] = dis[i];

  relax_edges(adj, cost, distance2); // Running it |V|th time to identify negative cycle nodes
  relax_edges(adj, cost, distance2); //Running it |V+1|th time to identify the first node of the negative cycle.


  for(int i=0;i<distance2.size();i++){
    //std::cout<<distance2[i]<<" "<<dis[i]<<"\n";
    if(distance2[i]!=dis[i]){
        bfs(adj, shortest, i);
        shortest[i] = 0;
    }
    if (dis[i] < std::numeric_limits<long long>::max())
        reachable[i] = 1;       
  }
}

The problem is I can't even identify which test case it is failing on.

Answer 1

I can provide you with an example for which your implementation fails. I will also describe the solution for the problem.

After running relax_edges |V| - 1 times you can find all valid shortest paths from the source assuming there are no negative cycles. After relaxing for the |V|-th time you can find out whether there is any negative cycle reachable from the source (when any shortest distance decreases). However, this is not enough to say, for every node, whether it lies on a reachable negative cycle.

Have a look at the example below (INF states for the infinity).

As you can see, after the |V|-th relaxation we can say that there is a negative cycle reachable from the source (node 3). We know that because there are nodes (2 and 3) for which the shortest path from the source has just decreased. However, after two additional relaxations (as in your implementation) we still don't know that the node 0 lies on a negative cycle. It's shortest distance from the source is still the same as for |V| - 1 relaxations.

Please note the following. If a node lies on some negative cycle, it also lies on a negative cycle of length at most |V|. This is true for simple graphs and multigraphs, whatever is your case. Therefore, instead of running relax_edges once or twice in the second part of the algorithm, you should run it |V| times. This way you make sure that for each node there was a possibility to traverse the whole negative cycle containing it. After these |V| additional relaxations you can compare the resulting shortest distances to the ones you have got for the first |V| - 1 relaxations. If the shortest distance for any node is lower, then you can say for sure it is on a negative cycle reachable from the source.

Of course, the provided solution does not increase the time complexity which is still O(|V| * |E|). The only drawback is a higher constant.

In the problem statement you have also mentioned that you need to return the shortest path if it exists. However, I can't see the relevant part it in the code you have provided. If this is also a missing thing, you just need to remember the predecessor of a node whenever you update the distance during the relaxation. A good and simple example of updating predecessors you can find on Wikipedia. If you have a predecessor for each node for which the shortest path exists, you can just follow the path backwards until reaching the source.

EDIT:

@ead showed that I've taken the requirement "2" too literally so I'm improving my answer. The algorithm I've presented can tell for each node whether it is a a part of a negative cycle reachable from the source. However, there may be a node which is not itself a part of any negative cycle but you can reach this node from a negative cycle reachable from the source. Therefore, to say that a shortest path to some node exists, you have to make sure that it is not reachable from any negative cycle reachable from the source.

A very reasonable solution, as @ead presented, is to run a graph search (DFS or BFS) from all nodes which are detected as a part of negative cycle during the |V|-th relaxation. For example, whenever you do shortest[i] = 0, you also add the node i to a queue. Then, you can run a single BFS with multiple starting nodes which are already present in the queue. Each node visited during this BFS is a part of a negative cycle reachable from the source and therefore there is no shortest path to it.

EDIT 2:

The approach with BFS is generally correct but I think your implementation is wrong. I can't see the point of checking if seen[t] == 3. You just need to remember, for each node, whether is has been visited during the graph search. Equivalently, you can mark as seen each node whenever it's pushed to the queue. Here is a fixed version of the BFS:

void bfs(vector<vector<int>>& adj, vector<int>& shortest, int s) {
    vector<int> seen(adj.size(), 0);

    queue<int> q;
    q.push(s);
    seen[s] = 1;

    while (!q.empty()) {
        int t = q.front();
        q.pop();

        for (int i = 0; i < adj[t].size(); ++i) {
            if (!seen[adj[t][i]]) {
                q.push(adj[t][i]);
                seen[adj[t][i]] = 1;
            }
        }
    }

    for (int i = 0; i < seen.size(); ++i) {
        if (seen[i] > 0) {          
            shortest[i] = 0;
        }
    }
}

I would also recommend creating the queue inside shortest_paths function and pushing to it each node which satisfies distance2[i] != dis[i]. Then you need to run BFS only once with an initialized queue.

Answer 2

I think you misinterpret the problem. In my opinion 2. should be:

If the node is reachable but is apart of from a reachable negative cycle and therefore, there is no shortest path (output as -)

Because clearly, one could run to the negative cycle, make arbitrary number of cycles and than run to your destination.

The second problem is, that |V|+1 iterations of relax_edges is not enough even to find all nodes on a negative cycle.

One possible way to solve the problem would be:

1. Run |V|-1 iterations of relax_edges
2. Run one iteration more of relax_edge to find some nodes on negative cycles. It's guaranteed, that for every negative cycle you will detect at least one node.
3. Run bfs or dfs from these detected nodes to find all nodes reachable from negative cycles (no well defined shortest path to these ones).

Edit: The following example shows, that the @Ardavel's suggestion to run relax_edges for 2*|V| times will not work:

After running relax_edges for 8 times, one would think, that the shortest path from 1 to 4 is directly to take the edge 1->4. However, the is no shortest path, because one could run to 2, than run more than 2000 times in the negative cycle (2<->3) and only than take the exit to 4.

To detect this, you would have to execute relax_edge more than 2000 times!

This is the reason you should do bfs/dfs/other algorithm of your liking after you have detected first nodes in negative cycles.