[그래프] 벨만-포드 알고리즘

벨만-포드 알고리즘

- 앞서 포스팅한 다익스트라와 유사한 최단경로 알고리즘입니다.

- 다익스트라와의 차이점은 가중치가 음수가 포함된 상황에서도 적용 가능하다는 특징입니다.

- 정점의 개수가 N이라면 시작 노드를 제외한 (N-1)회 반복문을 수행하여 최단 경로를 구할 수 있습니다. 

 

www.acmicpc.net/problem/11657

11657번: 타임머신

 

public static void checkedTimeMachine() {
    minTime[1] = 0;

    for(int i=0; i<N-1; i++) {
        for(Bus bus: buses) {
            int s = bus.start;
            int e = bus.target;
            
            if(minTime[s] == MAX) continue;
            if(minTime[e] > minTime[s] + bus.time) {
                minTime[e] = minTime[s] + bus.time;
            }
        }
    }
}

 반복문을 왜 (N-1)회 반복하는지 궁금해 결과값을 출력하면서 확인해봤습니다. 해당 문제는 1번 노드에서 다른 노드까지 이동하는데 최소 시간을 구하는 문제이며, 반복문이 한번 돌 때마다 1번 노드로 부터 특정한 하나의 노드까지의 최소 비용이 계산됩니다. 즉, [반복문 1번 = 하나의 노드까지의 최소 비용]