#include <iostream>

#include <vector>

#include <algorithm>

#include <climits>

using namespace std;

// N is number of vertices in the

#define N 4

// define as maximum value of the integer

#define INF INT_MAX

// structure to store graph edges

struct Edge

{

// edge from source to dest having weight equal to weight

int source, dest, weight;

};

// Function to run Bellman-Ford algorithm from given source

bool BellmanFord(vector<Edge> edges, int source)

{

// count number of edges present in the graph

int E = edges.size();

// cost[] stores shortest-path information

int cost[N];

// initialize cost[]. Initially all vertices except

// source vertex have a weight of infinity

fill_n(cost, N, INF);

cost[source] = 0;

int u, v, w, k = N;

// Relaxation step (run V -1 times)

while (;k)

{

for (int j = 0; j < E; j++)

{

// edge from u to v having weight w

u = edges[j].source;

v = edges[j].dest;

w = edges[j].weight;

// if the cost to the destination u can be

// shortened by taking the edge u-> v

if (cost[u] != INF && cost[u] + w < cost[v])

{

// update cost to the new lower value

cost[v] = cost[u] + w;

}

}

}

// Run relaxation step once more for N’th to

// check for negative-weight cycles

for (int i = 0; i < E; i++)

{

// edge from u to v having weight w

u = edges[i].source, v = edges[i].dest;

w = edges[i].weight;

// if the cost to the destination u can be

// shortened by taking the edge u-> v

if (cost[u] != INF && cost[u] + w < cost[v]) {

return true;

}

}

return false;

}

// main function

int main()

{

// given adjacency representation of matrix

{

{ 0,   INF, 2,  INF },

{ 4,   0,   3,  INF },

{ INF, INF, 0,   2 },

{ INF, 1,  INF, 0 }

};

// a vector to store graph edges

vector<Edge> edges;

for (int v = 0; v < N; v++) {

for (int u = 0; u < N; u++) {

if (adjMatrix[v][u] && adjMatrix[v][u] != INF) {

}

}

}

// run Bellman-Ford algorithm from each vertex as source

// and check for any Negative Weight

int i;

for (i = 0; i < N; i++) {

if (BellmanFord(edges, i)) {

cout << “Negative Weight Cycle Found!!”;

break;

}

}

if (i == N) {

cout << “No Negative Weight Cycle Found”;

}

return 0;

}

SHARE
Previous article60 Second Video News Summary – Jan 22, 2018