Bellman Ford算法在未知测试案例中失败
sil*_*dev 3 algorithm graph bellman-ford
我正在为过去的课程之一设置问题。我应该实现Bellman Ford Algorithm，这样从源头上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;
}
}
问题是我什至无法确定它在哪个测试用例上失败。
我可以为您提供一个实施失败的示例。我还将描述该问题的解决方案。
经过运行relax_edges |V| - 1时间后，假设没有负循环，您可以找到源中所有有效的最短路径。第三|V|次放松之后，您可以找出从源头是否可以到达任何负周期（当最短距离减小时）。但是，这还不足以对每个节点说它是否处于可到达的负周期上。
看下面的例子（INF无穷大的状态）。
如您所见，在|V|第-次松弛之后，我们可以说从源（节点3）可以到达一个负周期。我们知道，因为有些节点（2和3）距源的最短路径刚刚减少。但是，经过两次额外的放松（如在您的实现中一样），我们仍然不知道该节点0处于负周期。与来源的最短距离仍然与|V| - 1放松时的距离相同。
请注意以下事项。如果节点位于某个负周期上，那么它最多也位于一个长度为负的周期上|V|。无论您是哪种情况，对于简单图形和多图形来说都是如此。因此，relax_edges应该在算法第二次运行，而不是在算法的第二部分运行一次或两次|V|。这样，您可以确保每个节点都有可能遍历包含该节点的整个负循环。这些|V|额外的放松之后，您可以将最短的距离与第一次|V| - 1放松所得到的距离进行比较。如果任何节点的最短距离都较小，则可以肯定地说它处于从源可达的负周期内。
当然，所提供的解决方案不会增加仍然为O（| V | * | E |）的时间复杂度。唯一的缺点是常数较高。
在问题陈述中，您还提到了如果存在最短路径，则需要返回最短路径。但是，在您提供的代码中看不到相关部分。如果这也是一件丢失的事情，那么只要在松弛期间更新距离，您只需要记住节点的前身即可。一个很好的简单示例，可以在Wikipedia上找到更新前辈的示例。如果对于存在最短路径的每个节点都有一个前任，则可以向后跟随路径，直到到达源。
编辑：
@ead表明我从字面上理解了要求“ 2”，因此我正在改善答案。我提出的算法可以告诉每个节点它是否是从源头可以到达的负周期的一部分。但是，可能有一个节点本身并不是任何负周期的一部分，但是您可以从源可到达的负周期到达此节点。因此，要说存在到某个节点的最短路径，则必须确保从源可到达的任何负循环中都无法到达该路径。
如@ead所示，一个非常合理的解决方案是从所有节点运行图搜索（DFS或BFS），这些图被检测为在|V|第-次松弛期间负周期的一部分。例如，每当您执行时shortest[i] = 0，您还将节点添加i到队列中。然后，您可以使用队列中已经存在的多个起始节点来运行单个BFS。在此BFS期间访问的每个节点都是可从源到达的负周期的一部分，因此没有最短的路径。
编辑2：
BFS的方法通常是正确的，但我认为您的实现是错误的。我看不出检查是否要点seen[t] == 3。您只需要记住，对于每个节点，在图搜索期间是否已访问过该节点。同样，seen只要将其推入队列，就可以将其标记为每个节点。这是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_paths函数内部创建队列，并将满足条件的每个节点推送到该队列distance2[i] != dis[i]。然后，您只需要在初始化队列中运行一次BFS。