벨만-포드 알고리즘

벨만-포드 알고리즘은 양의 가중치만 적용할 수 있는 다익스트라 알고리즘과 달리 음의 가중치도 적용할 수 있단는 이점이 있다. 다음은 벨만-포드 알고리즘을 벡터를 이용하여 구현한 코드이다.

#include <iostream>
#include <vector>

#define MAX 501
#define INF 987654321
using namespace std;


int n, m; //정점, 간선
long long bellman[MAX];
vector<pair<pair<int, int>, int>> edge;

void bellman_ford()
{
	bellman[1] = 0;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j < edge.size(); j++)
		{
			int from = edge[j].first.first;
			int to = edge[j].first.second;
			int cost = edge[j].second;
			if (bellman[from] == INF)
				continue;
			if (bellman[to] > bellman[from] + cost)
			{
				bellman[to] = bellman[from] + cost;
			}
		}
	}
	for (int i = 0; i < edge.size(); i++)
	{
		int from = edge[i].first.first;
		int to = edge[i].first.second;
		int cost = edge[i].second;
		if (bellman[from] == INF)
			continue;
		if (bellman[to] > bellman[from] + cost) 
		{
			//음의 사이클이 존재하는 경우
			cout << "negative cycle\n";
			return;
		}
	}
	//음의 사이클이 존재하지 않는 경우
	cout << "not negative cycle\n";
}

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		bellman[i] = INF;
	}
	for (int i = 0; i < m; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		edge.push_back({ {a,b},c });
	}
	bellman_ford();
	return 0;
}

참고: https://yabmoons.tistory.com/380