Bellman-ford邻接矩阵不检测负循环的单源最短路径

Question

我曾尝试实现Bellman-ford单源最短路径的邻接矩阵，但它并没有检测到负循环中的一个顶点

同样的算法适用于边缘列表，但在相邻矩阵中给出了误差

我的代码：

#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时有一个-ve循环-

Answer 1

在第二个循环中，如果dist[i]已设置为INT\u MIN且matrix[i][j]为负值，则dist[i]矩阵[i][j]可能通过整数溢出的方式表现出未指定的行为。实际上，求和会变成一个大的正数，然后条件dist[j]