벨만 포드 알고리즘

모든 간선을 탐색하면서

A->B 보다 A->V[i]->B가 더 빠를때 갱신.

한편 dist[A]가 INT_MAX일 경우 계산해봤자 어차피 false일테니까 컨티뉴.

위의 계산을 V-1번 반복하여 최적화된 답을 찾음.

한편 마지막 V번 반복을 하였을 때 만약 값이 갱신되는 Vertex가 있다면 음수 사이클이 있다는 것을 의미한다.

template <typename FIRST, typename SECOND, typename THIRD>
class triple {
public:
	FIRST first;
	SECOND second;
	THIRD third;
	triple(FIRST a, SECOND b, THIRD c) {
		first = a;
		second = b;
		third = c;
	}
};

bool BellmanFord(vector<int> &dist, vector<triple<int, int, int>> &edge, int V, int E, int StartNode) {
	bool hasMinusCycle = false;

	for (int i = 1; i <= V; i++) {
		dist[i] = INT_MAX;
	}
	dist[StartNode] = 0;
	for (int i = 1; i <= V; i++) {
		for (auto nowEdge : edge) {
			int from = nowEdge.first;
			int to = nowEdge.second;
			int weight = nowEdge.third;

			if (dist[from] == INT_MAX) continue;
			if (dist[to] > dist[from] + weight) {
				dist[to] = dist[from] + weight;

				if (i == V) hasMinusCycle = true;
			}
		}
	}
	return hasMinusCycle;
}