벨만포드

•  정의
  • 최단거리를 구하는 알고리즘
  • 특정 출발 노드에서 다른 모든 노드까지의 최단 경로를 탐색한다
  • 음수 갖우치가 에지에 있어도 수행할 수 있다
  • 전체 그래프에서 음수 사이클 존재여부를 판단할 수 있다
  • 시간 복잡도는 O(VE)
• 핵심 이론
  • 에지 리스트로 그래프를 구현하고 최단 경로 리스트 초기화 하기
    • 
    • 에지를 중심으로 동작하므로 에지 리스트로 구현한다
    • 출발 노드는 0, 나머지는 무한대로 초기화 해준
  • 모든 에지를 확인해 정답 리스트 업데이트하기
    • 
    • 업데이트 반복 회수는 노드 개수 -1로 노드 개수가 N개이고 음수 사이클이 없을 경우 특정 두 노드의 최단 거리를 구성할 수 있는 에지의 최대 개수가 N-1이기 때문이다
    • 모든 에지 E =(s,e,w)에서 다음 조건을 만족하면 업데이트를 실행한다
      • D[s] != INF && D[e] > D[s] + w 일때 D[e] = D[s]+w로 리스트를 업데이트 함
    • 업데이트 반복 횟수가 K번이라면 해당 시점에 정답 리스트 값은 시작점에서 K개의 에지를 사용했을 때 각 노드의 최단거리이다
    • 음수 사이클이 없을 때 N-1번 에지를 사용 횟수를 반복하면 출발 노드와 모든 노드간 최단 거리를 알려주는 리스트가 완성되며, 이 그래프에 음수 사이클 존재 유무를 확인해야 한다
  • 음수사이클 유무 확인하기
    • 
    • 모든 에지를 한번씩 다시 사용해 업데이트되는 노드가 발생하는 지 확인하는 것이다
    • 업데이트가 되는 노드가 발생시 음수 사이클이 존재한다는 의미이다
    • 이때 도출한 정답 리스트가 무의미하고 최단 거리를 찾을 수 없는 그래프라는 의미가 되는 것이다
• 문제 특징
  • 코테에선 최단 거리를 구하는 문제보다 음수 사이클을 판별하는 문제가 더 빈번하게 출제가 된다
  • 따라서 마지막에 한번 더 모든 에지를 사용해 업데이트되는 노드가 발생하는지를 파악하여 음수 사이클이 존재하는지 파악해야 한다
• 구현

#include <iostream>
#include <vector>
#include <climits>

using namespace std;
#define INF INT_MAX

struct Edge
{
	int start, end;
	long long score;
};

void BellmanFord(vector<Edge> edge, int n, int m, int score)
{
	vector<long long> d(n+1, INF);
	d[1] = 0;

	for (int i = 1; i < n; i++)
	{
		for (Edge e : edge)
		{
			if (d[e.start] != INF && d[e.end] > d[e.start] + e.score)
				d[e.end] = d[e.start] + e.score;
		}
	}

	bool negative{};

	for (int i = 1; i <= n; i++)
	{
		for (Edge e : edge)
		{
			if (d[e.start] != INF && d[e.end] > d[e.start] + e.score)
			{
				cout << "음의 사이클 존재" << endl;
				return;
			}
		}
	}

	for (int i = 2; i <= n; i++)
	{
		if (d[i] != INF)
			cout << d[i] << endl;
		else
			cout << "-1\n";
	}
}

int main()
{
	int n{}, m{};
	cin >> n >> m;

	vector<Edge> edge(m);
	for (int i = 0; i < m; i++)
	{
		cin >> edge[i].start >> edge[i].end >> edge[i].score;
	}

	BellmanFord(edge, n, m, 1);
}