Bellman ford algorithm implemention

help
, , ,
1

can somebody tell me what is wrong with my implementation of bellman ford algo.

Here’s my code

//Bellman-Ford algorithm
#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;

vector<int> dist;
vector<vector<int> > vec;
int n;
void bell_for(int src)
{
	dist.resize(n+1, INT_MAX);
	src--;
	dist[src] = 0;
	for(int i=1;i<n;i++)//run n-1 times
	{
		for(int j=0;j<n;j++)//for every edge joining j and k
			for(int k=0;k<n;k++)
			{
					if(vec[j][k] == -1 || dist[j] == INT_MAX || k== src)
						continue;
						dist[k] = min(dist[k], dist[j] + vec[j][k]);
			}
			/*for(int h=0;h<n;h++)
				cout << dist[h] << " ";
				cout << endl; */
	}
	
}
int main()
{
	int m; cin  >> n >> m;// m is no of edges|| n is no of vertices
	vec.resize(n+1, vector<int> (n+1,-1));

	for(int j=0;j<n;j++)
		for(int k=0;k<n;k++)
		{
			vec[j][k] = -1;
		}
	for(int i=0;i<m;i++)
	{
		int v1,v2,weight;
		cin >> v1 >> weight >> v2;
		v1--; v2--;
		vec[v1][v2] = weight;
		vec[v2][v1] = weight;
	}
	/*for(int j=0;j<n;j++)
	{
		for(int k=0;k<n;k++)
			cout << vec[j][k] << " ";
			cout << endl;
	}
			*/
	int source;
	cin >> source;
	bell_for(source);
	for(int i=0;i<n;i++)
		cout << dist[i] << endl;	
}
/*
8 10
1 4 2
1 -2 3
2 -1 3
3 1 4
4 1 5
5 6 6
4 -2 6
4 8 7
6 -4 7
7 2 8
*/
2

If you are doing a bellman-ford, it would be better to use an edge list

3

I know but i just want to know what is wrong with this code. Thanks anyway

4

You are using a weight value of -1 to denote that no edge exists for the particular pair of vertices, however an actual edge weight of -1 is also possible. So your code will treat that edge as if it is not there.
Also you are taking each input edge to be bidirectional, but if a bidirectional edge has negative weight it becomes a negative-weight cycle in itself. As I’m sure you know, a shortest path between a particular pair of vertices may not exist if the graph contains any negative-weight cycles.
Apart from this I think the code is okay!

5

  1. vec.resize(n+1, vector (n+1,-1)); You don’t need a vector of n+1 elements; just of size n each being a vector of size n. vec.resize(n, vector (n,-1)); Also, -1 is a valid negative weight. You may want to use INT_MAX instead to initialize the new vectors.

  2. cin >> v1 >> weight >> v2;
    v1–; v2–; Validate that v1 and v2 are within bounds and that v1 is not same as v2. Also, don’t treat them as bidirectional else you cannot accept negative weights. Only assign the weight to vec[v1][v2] = weight.

  3. cin >> source; Validate source to be within bounds of (0, n-1) inclusive.

  4. Your Bell_for() function can terminate early if nothing changed in the “dist” vector for any iteration.

  5. The second “for” loop in Bell_for() should start with j = src and not j = 0; (for(int j=0;j<n;j++)//for every edge joining j and k)

6

Thanks Idk what was running in my mind then

7

Thanks!!!