I have tried implementing Bellman ford SSSP for adjacency matrix, but it is not detecting one of the vertices in the negative cycles
This is what the graph looks like:
My code:
#include <bits/stdc++.h>
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 should be -INF at 0->3 but it gives -3
Aucun commentaire:
Enregistrer un commentaire