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

Question

I have tried implementing Bellman ford Single Source Shortest Path for adjacency matrix, but it is not detecting one of the vertices in the negative cycles

the same algorithm works for edge list, but gives error in adjacency matrix

This is what the graph looks like:

My code:

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

OUTPUT :

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

there is a -ve cycle at 2->4->3, but my code only detects 2 and 4

Answer 1

In the second loop, dist[i] + matrix[i][j] may exhibit unspecified behavior by way of integer overflow if dist[i] is already set to INT_MIN and matrix[i][j] is negative. In practice, the sum wraps around to a large positive number, and then the condition dist[j] > (dist[i] + matrix[i][j]) doesn't hold, and dist[j] is not updated.