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

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->4->3 处有一个 -ve 循环，但我的代码只检测到 2 和 4

Answer 1

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

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

Bellman ford single source shortest path for adjacency matrix not detecting negative cycle

c++

c++11

shortest-path

bellman-ford