벨만포드 알고리즘

저도 나재원님의 댓글에 동의합니다.

i를 간선을 사용한 개수로 생각하고 코드를 짠다면 dist 를 2차원 배열로 만들어주거나 tmp 배열을 따로 만들어 값을 받아놨다가 갱신해야 맞는 코드인거 같습니다.

물론 최악의 경우 i가 N-1번 반복해야 답을 구할 수 있기 때문에  코드에 대한 문제는 없겠지만 앞부분의 설명과 코드가 매칭이 되지 않는것 같습니다

유재용님이 말씀하신 것처럼 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로 릴렉스 될 것 같습니다.

설명해주신 흐름과 코드의 흐름이 약간 매치가 안돼서 혼란이 오는 것 같습니다. 다시 한 번 정확하게 짚어주시면 감사드리겠습니다.

간선 한번만 이용하여야 하는 경우에서,

1, 2, 3, 4, 5, 도시별로 0, 5, 4, 무한대, 무한대

가 나와야하는데요, 간선 한번만 이용하는 경우 계산시, 2번째 도시로 가는 5가 계산된 상태에서 2 3 -3 간선 계산을 하니 

3번 도시 최솟값이 5- 3 = 2가 됩니다. 이걸 질문하신듯 합니다!

감사합니다^^

간선 정보의 입력순서가 꼭 그 경로순으로 입력되어 있다고 생각하면 안됩니다.  뒤죽박준 순으로 입력될 수 도 있습니다.

2 3 -3

1 2 5

과 같이 입력될 수 도 있습니다.

또는 문제지에 있는 입력순으로 들어왔다 하더라도 출발도시를 3, 도착도시를 5라 해놓고 2 5 13 간선을 2 5 1로 수정하고 해보세요. 안쪽 for문 한번으로 3에서 5로 가는 최소비용값 9가 계산되지 않습니다.

앗 저도 이것에 대해 질문하고 싶었는 데. 안 쪽 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