Answers for "bellman ford algorithm"

bellman ford algorithm

//by YASH DHOKIA
//to find the single source shortest paths using Bellman-Ford algorithm

#include<bits/stdc++.h>
using namespace std;

class Edge {

	public:
		int src,des,weigth;
};

vector<int> bellman(Edge *edge,int v,int e) {

	vector<int> dist(v,INT_MAX);
	dist[0]=0;
	for(int i=0; i<v-1; i++) {
		for(int j=0; j<e; j++) {
			if(dist[edge[j].des]>dist[edge[j].src]+edge[j].weigth)
			        dist[edge[j].des]=dist[edge[j].src]+edge[j].weigth;
		}
	}
	for( int j=0; j<e; j++)
		if(dist[edge[j].des]>dist[edge[j].src]+edge[j].weigth)
		        cout<<"negative weigth cycle present in this graph";
	return dist;
}

int main() {

	int v,e;
	cin>>v>>e;
	Edge* edge=new Edge[e];
	for(int i=0; i<e; i++) {
		int s,d,w;
		cin>>s>>d>>w;
		edge[i].src=s;
		edge[i].des=d;
		edge[i].weigth=w;
	}

	vector<int> dist(v);
	dist=bellman(edge,v,e);

	for(int i=0; i<dist.size(); i++)
		cout<<i<<" "<<dist[i]<<" "<<endl;
		
	return 0;
}

/*
5 9
0 1 4
0 2 2
1 3 2
1 2 3
1 4 3
2 1 1
2 3 4
2 4 5
4 3 -5
*/

bellman ford code in c++

#include<iostream>
#define MAX 10
using namespace std;
typedef struct edge
{
  int src;
  int dest;
  int wt;
}edge;
void bellman_ford(int nv,edge e[],int src_graph,int ne)
{
  int u,v,weight,i,j=0;
  int dis[MAX];
  
  /* initializing array 'dis' with 999. 999 denotes infinite distance */
  for(i=0;i<nv;i++)
  {
    dis[i]=999;
  }
    
  /* distance of source vertex from source vertex is o */
  dis[src_graph]=0;
  
  /* relaxing all the edges nv - 1 times */
  for(i=0;i<nv-1;i++)
  {
    for(j=0;j<ne;j++)
    {
      u=e[j].src;
      v=e[j].dest;
      weight=e[j].wt;
    
      if(dis[u]!=999 && dis[u]+weight < dis[v])
      {
        dis[v]=dis[u]+weight;
      }  
    }
    
  }
  
  /* checking if negative cycle is present */
  for(j=0;j<ne;j++)
  {
    u=e[j].src;
    v=e[j].dest;
    weight=e[j].wt;
    
    if(dis[u]+weight < dis[v])
    {
      cout<<"\n\nNEGATIVE CYCLE PRESENT..!!\n";
      return;
    }  
  }
  
  cout<<"\nVertex"<<"  Distance from source";
  for(i=1;i<=nv;i++)
  {
    cout<<"\n"<<i<<"\t"<<dis[i];
  }
}
int main()
{
  int nv,ne,src_graph;
  edge e[MAX];
  
  cout<<"Enter the number of vertices: ";
  cin>>nv;  
  
  /* if you enter no of vertices: 5 then vertices will be 1,2,3,4,5. so while giving input enter source and destination vertex accordingly */
  printf("Enter the source vertex of the graph: ");
  cin>>src_graph;  
  
  cout<<"\nEnter no. of edges: ";
  cin>>ne;
  
  for(int i=0;i<ne;i++)
  {
    cout<<"\nFor edge "<<i+1<<"=>";
    cout<<"\nEnter source vertex :";
    cin>>e[i].src;
    cout<<"Enter destination vertex :";
    cin>>e[i].dest;
    cout<<"Enter weight :";
    cin>>e[i].wt;  
  }
  
  bellman_ford(nv,e,src_graph,ne);
  
  return 0;
}

bellman ford algorithm

//It is an algorithm to detect negative cycle in a graph as well as can we used to find the shortest distance from source

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int u,v,wt;
    node(int first,int second ,int weight)
    {
        u=first;
        v=second;
        wt=weight;
    }
};
int main()
{
   int vertex,edges;
   cout<<"ENTER THE NUMBER OF VERTEX AND EDGES:"<<endl;
   cin>>vertex>>edges;
   vector<node>adj;
   cout<<"ENTER THE LINKS:"<<endl;
   int a,b,w;
   for(int i=0;i<edges;i++)
   {
       cin>>a>>b>>w;
       adj.push_back(node(a,b,w));
   }
   int src;
   cout<<"ENTER THE SOURCE"<<endl;
   cin>>src;
   int large=100000;
   vector<int>dist(vertex,large);
   dist[src]=0;
   for(int i=1;i<=vertex-1;i++)
   {
       for(auto it:adj)
       {
           if(dist[it.u]+it.wt<dist[it.v])
           {
               dist[it.v]=dist[it.u]+it.wt;
           }
       }
   }
   int flag=0;
   for(auto it:adj)
       {
           if(dist[it.u]+it.wt<dist[it.v])
           {
               cout<<"NEGATIVE CYCLE DETECTED:"<<endl;
               flag=1;
               break;
           }
       }
       if(!flag)
       {
           for(int i=0;i<vertex;i++)
           {
               cout<<i<<" "<<dist[i]<<endl;
           }
       }
       return 0;
}

bellman ford algorithm cp algorithm

struct edge
{
    int a, b, cost;
};

int n, m, v;
vector<edge> e;
const int INF = 1000000000;

void solve()
{
    vector<int> d (n, INF);
    d[v] = 0;
    for (int i=0; i<n-1; ++i)
        for (int j=0; j<m; ++j)
            if (d[e[j].a] < INF)
                d[e[j].b] = min (d[e[j].b], d[e[j].a] + e[j].cost);
    // display d, for example, on the screen
}

bellman ford algorithm

#include <vector>
#include <iostream>
using namespace std;

#define INF 99999;

struct Edge {
	int u, v, w;
};

int V; 							// Number of verticies.
vector<vector<Edge>> adjList;	// Adjacency list.
vector<vector<int>> adjMatrix;	// Adjacency matrix.

// With adjacency list.
int* shortestPath(int src) {
	int dist[V];
  	for (int u = 0; u < V; ++u)
      dist[u] = INF;
  	dist[src] = 0;

	for (int i = 0; i < V - 1; ++i)
		for (int u = 0; u < V; ++u)
			for (Edge e : adjList[u])
				if (dist[e.u] + e.w < dist[e.v])
          			dist[e.v] = dist[e.u] + e.w;
  
  	for (int u = 0; u < V; ++u)
		for (Edge e : adjList[u])
        	if (dist[e.u] + e.w < dist[e.v])
            	throw std::runtime_error("negative loop detected")
    
    // contains the shortest dist between src and each vertex.
  	return dist;
}

// With adjacency matrix.
int* shortestPath(int src) {
	int dist[V];
  	for (int u = 0; u < V; ++u)
      dist[u] = INF;
  	dist[src] = 0;

	for (int i = 0; i < V - 1; ++i)
		for (int u = 0; u < V; ++u)
			for (int v = 0; v < V; ++v)
				if (dist[u] + adjMatrix[u][v] < dist[v])
          			dist[v] = dist[u] + adjMatrix[u][v];
  
  	for (int u = 0; u < V; ++u)
		for (int v = 0; v < V; ++v)
        	if (dist[u] + adjMatrix[u][v] < dist[v])
            	throw std::runtime_error("negative loop detected")
    
    // contains the shortest dist between src and each vertex.
  	return dist;
}