인프런 커뮤니티 질문&답변
작성한 질문수
벨만포드 알고리즘
작성
·
474
1
안녕하십니까 좋은 강의 감사드립니다.
벨만포드 알고리즘코드 관련하여 질문이있습니다.
for(i=1; i<n; i++){
for(j=0; j<Ed.size(); j++){
int s=Ed[j].s;
int e=Ed[j].e;
int w=Ed[j].val;
if(dist[s]!=2147000000 && dist[s]+w<dist[e]){
dist[e]=dist[s]+w;
}
}
}
여기서 바깥 for문이 i에 따라 1일때는 한번만에 가는 경우, 2일 때는 두번만의 가는 경우 ..... n-1번만에 가는경우 라고 설명 해 주셨는데 바깥 for문이 없더라도 안 쪽 for문 만으로 n-1번만에 가는 경우를 다 따지는 거 같은데 혹시 제가 잘못 이해한 것 인지... 입력이 vertex number 순으로 순차적으로 받게 되는데 예를들어 i가 1이고 안쪽 for 문을 j가 1일때 돌며 1->2 가는 것을 추가하여서 dist[2]=x를 넣게되면 그다음 j가 2가 될때는
dist[2]!=2147000000 조건에 걸리지 않게 되고 2에서 가는 경우의 수를 검토하게 되는데 그렇게 되면 이것은 두번만에 가는 경우가 되는것이 아닙니까??
답변 5
0
저도 나재원님의 댓글에 동의합니다.
i를 간선을 사용한 개수로 생각하고 코드를 짠다면 dist 를 2차원 배열로 만들어주거나 tmp 배열을 따로 만들어 값을 받아놨다가 갱신해야 맞는 코드인거 같습니다.
물론 최악의 경우 i가 N-1번 반복해야 답을 구할 수 있기 때문에 코드에 대한 문제는 없겠지만 앞부분의 설명과 코드가 매칭이 되지 않는것 같습니다
0
유재용님이 말씀하신 것처럼 i가 1인 상태에서 j가 2번 돌게되면 0,5,4,무한대,무한대인 상태인데 그 다음 j가 3번째로 돌 때, 2->3 경로를 계산하면 dist[2]+w < dist[3]이 되는데 이 때, dist[2]는 무한대가 아니라 5로 계산된 값이라서 결국 dist[3]이 2로 릴렉스됩니다. 그럼 결국 i가 1인 상태임에도 불구하고 1->2->3을 거친 값이 dist[3]에 들어가게 됩니다. 저는 "i가 1"이다의 의미를 "시작 노드로부터 한 번의 경로로 갈 때"로 이해했습니다. 제가 이해한 것이 틀렸는지 잘 모르겠습니다.
설명해주신대로 값이 릴렉스 되려면 dist를 인접행렬로 만들거나 해서 이전 경로횟수(0번)의 인덱스 값(2)에 +w를 해주어야할 것 같습니다 그래야 무한대+(-3) 이 되어 dist[3]이 4로 릴렉스 될 것 같습니다.
설명해주신 흐름과 코드의 흐름이 약간 매치가 안돼서 혼란이 오는 것 같습니다. 다시 한 번 정확하게 짚어주시면 감사드리겠습니다.
0
간선 한번만 이용하여야 하는 경우에서,
1, 2, 3, 4, 5, 도시별로 0, 5, 4, 무한대, 무한대
가 나와야하는데요, 간선 한번만 이용하는 경우 계산시, 2번째 도시로 가는 5가 계산된 상태에서 2 3 -3 간선 계산을 하니
3번 도시 최솟값이 5- 3 = 2가 됩니다. 이걸 질문하신듯 합니다!
0
감사합니다^^
간선 정보의 입력순서가 꼭 그 경로순으로 입력되어 있다고 생각하면 안됩니다. 뒤죽박준 순으로 입력될 수 도 있습니다.
2 3 -3
1 2 5
과 같이 입력될 수 도 있습니다.
또는 문제지에 있는 입력순으로 들어왔다 하더라도 출발도시를 3, 도착도시를 5라 해놓고 2 5 13 간선을 2 5 1로 수정하고 해보세요. 안쪽 for문 한번으로 3에서 5로 가는 최소비용값 9가 계산되지 않습니다.
음의 사이클이 안 나온다는 간선 정보라고 가정했을 때,
뒤죽박죽으로 입력 시 최소 값이 안 나온다면 간선 정보를 오름차순으로 정렬하고 이중for문을 for문으로 고쳐 써보면 어떨까 생각했는데요. 정렬을 한 번 하는 것보다 이중 for문으로 돌리는 게 결국 시간 복잡도가 덜 할까요?
0
앗 저도 이것에 대해 질문하고 싶었는 데. 안 쪽 j for loop만 돌아도 값이 나오는 것 같아서, 저도 같은 질문드립니다.
for (i = 1; i < n; i++) {
for (j = 0; j < Ed.size(); j++) {
int start = Ed[j].s; // 1, 1, 2,
int end = Ed[j].e; // 2, 3, 3,
int cost = Ed[j].val; // 5, 4, -3,
if (dist[start] != 2147000000 && dist[start] + cost < dist[end]) {
dist[end] = dist[start] + cost;
cout << i << "/" << j << " - " << "start : " << start << ", " << "end : " << end << ", " << "total cost : " << dist[end] << endl;
}
}
cout << i << endl;
}
1/0 - start : 1, end : 2, total cost : 5 1/1 - start : 1, end : 3, total cost : 4 1/2 - start : 2, end : 3, total cost : 2 1/3 - start : 2, end : 5, total cost : 18 1/4 - start : 3, end : 4, total cost : 7 1/6 - start : 4, end : 5, total cost : 14 1 2 3 4
안녕하세요^^
네. 맞습니다.
원래는 정말 1번만에 간 값만 1행에 있고, 2번만에 간 값만 2행에 있고 하려면 코드짜기 전에 그림을 그려서 이론을 설명한 방법처럼 dist배열을 2차원으로 잡아야 정확하게 할 수 있습니다. 코드는 제가 2차원 배열을 쓰지않고 1차원 배열에서 모든것을 해결하려고 하다보니 i가 1일때 한 번만에 가는 값만 있어야 하는데 특정 정점값은 앞에 1번만에 간게 적용된 값을 가지고 또 적용을 해서 2번만에 간 값으로 미리 적용될 수 있습니다.
유의할 점은 원 질문자님처럼 이중for문이 아닌 단일for문으로 벨만포드가 완성된다고 생각하면 안된다는 것입니다.