c++ - 贝尔曼福特单源最短路径的邻接矩阵未检测到负循环

Question

我曾尝试为邻接矩阵实现 Bellman Ford Single Source Shortest Path，但它没有检测到负循环中的顶点之一
相同的算法适用于边缘列表，但在邻接矩阵中给出错误
这是图表的样子:

我的代码:

#include <iostream>
#include <climits>
#include <vector>
using namespace std;

#define INF INT_MAX
#define NINF INT_MIN

void shortestpath(int src, vector<vector<int>> &matrix){
    int N = matrix.size();
    vector<int> dist(N, INF);
    vector<int> prev(N, 0);

    dist[src] = 0;
    for(int k = 0; k < N-1; k++){
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if(dist[i] != INF && matrix[i][j] && dist[j] > (dist[i] + matrix[i][j]) ){
                    dist[j] = dist[i] + matrix[i][j];
                    prev[j] = i;
                }
            }
        }
    }

    // for(int i = 0; i < N; i++)
    //     if(i != src)
    //         cout << src << " - " << i << "\t" << dist[i] << endl;
    // cout << "\n\n";

    // to check if -ve cycles exist or not
    for(int k = 0; k < N-1; k++){
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if(matrix[i][j] && dist[j] > (dist[i] + matrix[i][j]) ){
                    dist[j] = NINF;
                    prev[j] = -1;
                }
            }
        }
    }

    for(int i = 0; i < N; i++)
        if(i != src)
            cout << src << " - " << i << "\t" << dist[i] << endl;
    return ;
}

// Driver function
int main(){
    int V = 8;
    vector<vector<int>> matrix(V, vector<int>(V, 0));
    matrix[0][1] = 1;
    matrix[1][2] = 1;
    matrix[2][4] = 1;
    matrix[4][3] = -3;
    matrix[3][2] = 1;
    matrix[1][5] = 4;
    matrix[1][6] = 4;
    matrix[5][6] = 5;
    matrix[6][7] = 4;
    matrix[5][7] = 3;

    shortestpath(0, matrix);

    return 0;
}
 

输出 :

0 -> 1   =   1
0 -> 2   =  -2147483648
0 -> 3   =  -3
0 -> 4   =  -2147483648
0 -> 5   =  5
0 -> 6   =  5
0 -> 7   =  8

在 2->4->3 有一个 -ve 循环，但我的代码只检测到 2 和 4

Answer 1

在第二个循环中，dist[i] + matrix[i][j]如果 dist[i]，可能会通过整数溢出表现出未指定的行为已经设置为 INT_MIN和 matrix[i][j]是否定的。在实践中，总和环绕为一个很大的正数，然后条件 dist[j] > (dist[i] + matrix[i][j])不成立，和dist[j]没有更新。