문제

n개의 노드

m개의 양방향 양수 가중치 간선

n 개의 단방향 음수 가중치 간선

일때 총 가중치가 음수인 사이클이 존재하는지 여부를 조사하자.

접근

DFS로 백날 해보려했는데 안된다.

찾아보니 음수 사이클을 조사하는데는 벨만포드 알고리즘을 사용해야한다.

벨만포드 알고리즘은 음수 간선이 포함된 그래프에서 특정 노드에서 다른 노드들까지의 최단거리를 구할 수 있는 알고리즘이다. O(VE)의 시간복잡도를 가진다고 한다. 노드 개수 V 간선개수 E

개략적인 흐름은 N개의 노드가 있다면 N-1번의 사이클을 돌면서 i 번째 사이클에는 첫번째 노드에서 i번만에 접근할 수 있는 노드들의 최단거리를 갱신하는 방법이다.

그런데 음수 사이클이 있는 그래프에서 이과정을 무한번 사이클 반복한다면 음수인 간선을 무한번 돌며 최단거리를 무한히 줄일 수 있다. 그러면 이걸 잡아내면 우리가 목표하는 음수 사이클 존재 여부를 확인할 수 있다.

그렇다고 진짜 무한번 반복할 수는 없으니 n-1번의 사이클 이후 다음번 사이클에서도 갱신이 일어나는 것으로 음수 사이클을 입증할 수 있다.

상당히 잘못된 벨만포드

vector<vector<int>> edge(n, vector<int>(n)); // edge[i][j] = weight;

vector<int> min_dis(n, INF);

min_dis[1] =0 ;
for (int i = 0; i < n-1; i++) {
	for( int j = 0; j < n ; j++ ) {
		for( auto nxt : edge[j] ) {
			if ( min_dis[j] + nxt.second < min_dis[ nxt.first ] )
				min_dis[ nxt.first ] = min_dis[j] + nxt.second;

// test negative cycle

	for( int j = 0; j < n ; j++ ) {
		for( auto nxt : edge[j] ) {
			if ( min_dis[j] + nxt.second < min_dis[ nxt.first ] )
				cout << "음수사이클";

시간복잡도가 O(V^2 E)가 된다. 무언가 심히 잘못된 줄 알았지만 아니었다.!!

내부의 두개의 for문이 순회하는건 모든 간선 즉 O(E)였다. 그러니 잘 만든 코드다.