글 읽기 - 단절된 그래프와 벨만 포드 알고리즘 연관성에 대해 질문 드립니다.

dladydwo123 2년 전 0

벨만 포드 알고리즘은 table[start] = 0으로 설정하고

table[prev.start] != INF가 아닐 때 비용정보를 갱신하는 것으로 알고 있습니다.

하지만 만약에,

전제조건에 "간선의 가중치는 모두 양수이고"

1. table[start] = 0; //출발지점 명시

2. if(table[prev.start]!=INF) // 출발지점과 연결된 간선만 업데이트

라는 2가지 명령을 없애면,

N-1번의 간선 업데이트를 통해서 최종적으로 결정된

table배열에 table[idx] == INF가 갖는 의미는,

단절된 그래프들의 출발지점으로 볼 수 있는지 여부에 대해서 질문 드리고 싶습니다.

#include <iostream>
#include<vector>
#include<queue>
#include<utility>
#include<algorithm>

using namespace std;

int T, N, M, K;



int main() {
	cin >> T;
	for(int k=0; k<T; k++){
		cin >> N >> M >>K;
		
		vector<pair<int,int>> v[501];
		int table[501] = {0,};
		for(int i=1; i<=N; i++){
			table[i] = 1e8; // 단순 기준값으로의 역활을 한다.
		}
		//table[1] = 0; 출발지점을 따로 명시하지 않는다.
		
		for(int i=0; i<M; i++){
			int a, b,c;
			cin >> a >> b >> c;
			v[a].push_back({b,c});
			v[b].push_back({a,c});
		}
		
		for(int i=0; i<K; i++){
			int a, b,c;
			cin >> a >> b >> c;
			v[a].push_back({b,-1 * c});
		}
		
		
		for(int i=1; i<=N; i++){
			
			for(int j=1; j<=N; j++){
				int s = v[j].size();
				for(int k=0; k<s; k++){
					if(1){//table[j] != 1e8 라는 조건을 따로 검사하지 않고 일단 갱신한다.
						int ret = table[j] + v[j][k].second;
						table[v[j][k].first] = table[v[j][k].first] < ret ? table[v[j][k].first] : ret;
					}
				}
			}
		}
        
        int ans = 0;
		for(int i=1; i<=N; i++){
            if(table[i] == 1e8){
                ans++; // 단절된 그래프의 출발지점이라 볼 수 있다.
            }
        }
	}
	
	return 0;
}

paldad 2년 전 0

안녕하세요.

질문이 약간 명확하지 않은것 같습니다.

단절된 그래프의 출발지점 -> 연결 요소의 수를 의미하셨던 건가요?

위 질문주신 내용중

1. 모든 간선의 가중치가 양수이고 (-> 음수가 아니고, 라고 이해 하겠습니다)

2. 시작 정점으로부터의 비용을 0 으로 설정하지 않고.

3. if(table[prev.start]!=INF) 부분을 없애면,

그 어떤 완화 시도도 실패할 것입니다.

즉 table[here] + dist < table[there] 의 조건을 만족하는 경우가 존재하지 않기 떄문에, table[] 는 마지막에 모두 INF 값으로 남게 됩니다.

dladydwo123 2년 전 0

paldad

우선 답변감사드립니다. 제가 질문 자체를 잘못한거 같습니다.

답변 주신 것처럼, 모든 가중치가 양수면 당연히 44, 45, 46번째 줄에서 갱신이 일어나지 않는다는 것을 간과한거 같습니다.

질문의 의도는 사실, 1865번 문제를 table[start] = 0, if(table[prev.start]!=INF) 라는 조건문없을 때 문제가 해결되서 이를 이해하고자 질문을 올린건데,

웜홀 문제의 특성상 음수 가중치가 존재하기 때문에,44, 45, 46번째 줄에 갱신이 일어나서 최종적으로 음의 사이클을 가지게 하는 웜홀을, 출발지점으로 하는 table내의 모든 정점들이 갱신이 된다는 것으로 결론지었습니다.

jh05013 2년 전 0

이 문제 관련 논란을 모두 정리해 보았습니다.

https://www.acmicpc.net/board/...

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

단절된 그래프와 벨만 포드 알고리즘 연관성에 대해 질문 드립니다.

dladydwo123 2년 전 0

paldad 2년 전 0

dladydwo123 2년 전 0

paldad

jh05013 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말