bellman ford * -1 code example

Example: 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;
}