Bellman Ford
(library/graphs/bellman-ford.hpp)

• View this file on GitHub
• Last update: 2022-07-21 16:12:33-04:00
• Include: #include "library/graphs/bellman-ford.hpp"

Bellman Ford

Works in $\mathcal O(VE)$ for $V$ vertices and $E$ edges. Note that negative_cycle is the same as gen, but it doesn’t call gen_bad$.

Functions

• init(n): Initializes the variables.
• gen(src): Generates distances from src.
• negative_cycle(src)$: Finds a negative cycle if it exists. If it doesn’t, this returns an empty list.

Variables

• dist: Stores distances to each vertex. It’s infinity if you can’t reach it and negative infinity if you have a negative cycle.

Resources

• Benq

Verified with

• verify/aizu/aizu-GRL_1_B.test.cpp

Code

#pragma once

template <class T> struct BellmanFord {
	const T INF = std::numeric_limits<T>::max();
	int n; 
	std::vector<std::vector<int>> adj;
	std::vector<std::pair<std::pair<int, int>, T>> edges;
	std::vector<T> dist;

	void init(int n_) {
		n = n_;
		adj.assign(n, std::vector<int>());
		edges.clear();
		dist.assign(n, 0);
	}

	void ae(int u, int v, T w) {
		adj[u].push_back(v);
		edges.push_back({{u, v}, w});
	}   

	void gen_bad(int x) {
		if (dist[x] == -INF)
			return;
		dist[x] = -INF;
		for (auto& nxt : adj[x])
			gen_bad(nxt);
	}

	void gen(int src) {
		for (int i = 0; i < n; i++) 
			dist[i] = INF;
		dist[src] = 0;
		for (int i = 0; i < n; i++)
			for (auto& e : edges) 
				if (dist[e.first.first] < INF)
					dist[e.first.second] = std::min(dist[e.first.second], dist[e.first.first] + e.second);
		for (auto& e : edges) 
			if (dist[e.first.first] < INF && dist[e.first.second] > dist[e.first.first] + e.second)
				gen_bad(e.first.second);
	}
	
	std::vector<int> negative_cycle(int src = 0) {
		for (int i = 0; i < n; i++)
			dist[src] = INF;
		dist[src] = 0;
		std::vector<int> pre(n);
		for (auto& e : edges) 
			if (e.first.first == e.first.second && e.second < 0) 
				return {e.first.first};
		for (int i = 0; i < n; i++) 
			for (auto& e : edges) 
				if (dist[e.first.first] < INF)
					if (dist[e.first.second] > dist[e.first.first] + e.second) {
						dist[e.first.second] = dist[e.first.first] + e.second;
						pre[e.first.second] = e.first.first;
					}
		for (auto& e : edges) 
			if (dist[e.first.first] < INF)
				if (dist[e.first.second] > dist[e.first.first] + e.second) {
					int x = e.first.second;
					for (int i = 0; i < n; i++)
						x = pre[x];
					std::vector<int> cycle;
					for (int v = x; v != x || cycle.empty(); v = pre[v])
						cycle.push_back(v);
					reverse(cycle.begin(), cycle.end());
					return cycle;
				}
		return {};
	}
};

template <class T> struct BellmanFord {
	const T INF = std::numeric_limits<T>::max();
	int n; 
	std::vector<std::vector<int>> adj;
	std::vector<std::pair<std::pair<int, int>, T>> edges;
	std::vector<T> dist;

	void init(int n_) {
		n = n_;
		adj.assign(n, std::vector<int>());
		edges.clear();
		dist.assign(n, 0);
	}

	void ae(int u, int v, T w) {
		adj[u].push_back(v);
		edges.push_back({{u, v}, w});
	}   

	void gen_bad(int x) {
		if (dist[x] == -INF)
			return;
		dist[x] = -INF;
		for (auto& nxt : adj[x])
			gen_bad(nxt);
	}

	void gen(int src) {
		for (int i = 0; i < n; i++) 
			dist[i] = INF;
		dist[src] = 0;
		for (int i = 0; i < n; i++)
			for (auto& e : edges) 
				if (dist[e.first.first] < INF)
					dist[e.first.second] = std::min(dist[e.first.second], dist[e.first.first] + e.second);
		for (auto& e : edges) 
			if (dist[e.first.first] < INF && dist[e.first.second] > dist[e.first.first] + e.second)
				gen_bad(e.first.second);
	}
	
	std::vector<int> negative_cycle(int src = 0) {
		for (int i = 0; i < n; i++)
			dist[src] = INF;
		dist[src] = 0;
		std::vector<int> pre(n);
		for (auto& e : edges) 
			if (e.first.first == e.first.second && e.second < 0) 
				return {e.first.first};
		for (int i = 0; i < n; i++) 
			for (auto& e : edges) 
				if (dist[e.first.first] < INF)
					if (dist[e.first.second] > dist[e.first.first] + e.second) {
						dist[e.first.second] = dist[e.first.first] + e.second;
						pre[e.first.second] = e.first.first;
					}
		for (auto& e : edges) 
			if (dist[e.first.first] < INF)
				if (dist[e.first.second] > dist[e.first.first] + e.second) {
					int x = e.first.second;
					for (int i = 0; i < n; i++)
						x = pre[x];
					std::vector<int> cycle;
					for (int v = x; v != x || cycle.empty(); v = pre[v])
						cycle.push_back(v);
					reverse(cycle.begin(), cycle.end());
					return cycle;
				}
		return {};
	}
};

Back to top page