algorithm - Bellman Ford算法在未知测试案例中失败

Question

我正在为过去的一门课准备一套习题我应该实现Bellman-Ford算法，以便从源代码s，我必须找到以下内容：
如果无法从s访问节点（输出为*）
如果节点是可到达的，但是是负循环的一部分，因此没有最短路径（输出为-）
否则，输出从s到节点的最短路径
我已经编写了以下代码，但在未知的测试用例中失败了有人能帮我调试一下吗？

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

问题是我甚至不能确定它在哪个测试用例上失败。

Answer 1

我可以为您提供一个实现失败的示例。我还将描述这个问题的解决方案。
在运行relax_edges|V| - 1次之后，假设没有负循环，您可以从源中找到所有有效的最短路径。在放松了|V|第二次之后，你可以知道是否有来自源的任何负循环（当任何最短距离减小时）。然而，这还不足以说明，对于每个节点来说，它是否位于可到达的负循环上。
看看下面的例子（INF无限状态）。

正如你所看到的，在第次弛豫之后，我们可以说有一个负循环可以从源（节点3）到达。我们知道，因为有些节点（|V|和2）的源最短路径刚刚减少。然而，在两次额外的放松（如在您的实现中）之后，我们仍然不知道节点3处于负循环。它离放射源的最短距离仍然和放松一样。
请注意以下几点。如果一个节点位于某个负周期上，那么它也最多位于长度为负的周期上。对于简单图和多重图，不管是什么情况，都是这样因此，不要在算法的第二部分运行0一次或两次，而是应该运行|V| - 1次这样可以确保每个节点都有可能遍历包含它的整个负循环。在这些|V|附加松弛之后，您可以将得到的最短距离与第一次relax_edges松弛所得到的最短距离进行比较。如果任何节点的最短距离较低，则可以确定该节点处于可从源访问的负循环上。
当然，所提供的解决方案并没有增加仍然是O的时间复杂度。唯一的缺点是常数较高。
在问题陈述中，您还提到如果存在的话，您需要返回最短路径。但是，我在您提供的代码中看不到它的相关部分。如果这也是一个缺失的东西，那么只要在松弛期间更新距离时记住节点的前一个节点更新前置任务的一个简单好例子，您可以在Wikipedia上找到。如果每个节点都有一个最短路径存在的前驱，则可以沿着路径向后走直到到达源。
编辑：
@ead显示我已经把要求“2”太字面化了，所以我正在改进我的答案。我提出的算法可以判断每个节点是否是可以从源到达的负循环的一部分。但是，可能有一个节点本身不是任何负循环的一部分，但是您可以从一个可以从源到达的负循环到达该节点因此，假设存在某个节点的最短路径，则必须确保它不能从源到达的任何负周期到达。
正如@ead所提出的，一个非常合理的解决方案是从所有节点运行图搜索（dfs或bfs），这些节点在第次松弛期间被检测为负循环的一部分。例如，无论何时执行|V|，都会将节点|V|添加到队列中。然后，可以使用队列中已存在的多个启动节点运行单个bfs。在此bfs期间访问的每个节点都是负循环的一部分，可从源访问，因此没有到它的最短路径。
编辑2：
使用bfs的方法通常是正确的，但我认为您的实现是错误的。我看不出检查是否|V| - 1的意义您只需要记住，对于每个节点，在图搜索期间是否访问过。等价地，每当每个节点被推送到队列时，都可以将其标记为|V|。以下是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;
        }
    }
}

我还建议在 shortest[i] = 0函数中创建队列，并将满足 i的每个节点推送到队列中。然后您只需要使用初始化的队列运行一次bfs。