벨만-포드(Bellman-Ford) 알고리즘

벨만-포드(Bellman-Ford) 알고리즘은 하나의 시작 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이다.

다익스트라 알고리즘과 달리 간선의 가중치가 음수인 경우에도 최단 거리를 구할 수 있다.

단, 음수 사이클이 존재하지 않는 그래프에서만 정상적인 최단 거리 결과를 얻을 수 있다.

핵심 원리

모든 간선을 반복적으로 확인하면서 각 간선을 통해 갈 수 있는 더 짧은 경로가 있으면 계속 갱신한다.

이 과정을 반복하면 최단 거리가 점점 퍼지듯이 전파되고, 최종적으로 모든 정점까지의 최단 거리가 결정된다.

목적지의 현재 최단 거리(dist[e.to])보다 출발지를 거쳐 가는 거리(dist[e.from] + e.cost)가 더 작다면 갱신.

$dist[e.to] = min(dist[e.to],dist[e.from] + e.cost)$

단, 현재까지 도달한 적이 있는 정점(dist[e.from] != INF)만 이용해서 갱신한다.

알고리즘 동작 과정

1. 출발 노드 설정.

2. 최단 거리 테이블 초기화.

3. 다음의 과정을 V-1번 반복

   • 전체 간선 E개를 하나씩 확인.

   • 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신.

V-1번 반복하는 이유

한 정점에서 다른 정점까지의 최단 경로는 최대 V-1개의 간선을 사용하기 때문에 V-1번 반복한다.

만약 V-1번을 다 돌기 전이라도, 어떤 간선에 대해서도 거리 갱신이 한 번도 일어나지 않았다면 이미 모든 최단 거리가 확정된 것이므로 즉시 종료해도 된다.

특징 및 주의사항

시간복잡도: $O(V·E)$

음수 사이클

음수 사이클이 존재하면 사이클을 계속 돌면서 비용을 무한히 줄일 수 있기 때문에 최단 거리가 정의되지 않는다.

만약 음수 사이클이 발생하는지 체크하고 싶다면 3번의 과정을 한 번 더 수행한다.

이때 최단 거리 테이블이 갱신된다면 음수 간선 순환이 존재하는 것이다.

문제

LeetCode 787. Cheapest Flights Within K Stops

풀이

이 문제의 경우 음수 가중치가 없어 다익스트라로도 풀 수 있지만, "K번 이하 경유"라는 횟수 제한 때문에 벨만-포드가 훨씬 직관적이다.

다익스트라는 한 정점에서 다른 어떤 정점으로 가야 목적지까지 최소 비용일까 고민하는 정점 중심 알고리즘이다. 그래서 인접 리스트로 그래프를 구현해야 할 뿐만 아니라, 경유 횟수별 방문 처리도 따로 관리해야 하는 번거로움이 있다.

반면 벨만-포드는 간선 중심 알고리즘이다. 한 번의 루프에서 정보의 전파가 딱 한 번씩만 일어나게끔 임시 배열로 강제하기만 하면 정말 쉽게 구현할 수 있다.

import java.util.*;

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
    	//최단 거리 배열 초기화
        int[] dist = new int[n];
        Arrays.fill(dist, 1_000_000_000);
        dist[src] = 0; // 시작점 비용 0으로 설정

        // 벨만-포드 알고리즘 적용 (k번의 경유 → (k+1)개의 간선 수)
        for(int i=0; i<k+1; i++){
            // 이번 회차의 결과를 담을 임시 배열 생성
            // 원본을 참고하고 갱신은 temp에 하여, 한 루프에 한 칸의 전파만 되도록 강제함
            int[] temp = Arrays.copyOf(dist, n);

            for(int j=0; j<flights.length; j++){
                // 이전 단계에서 도달 가능했던 노드인 경우에만 갱신 진행
                if(dist[flights[j][0]] != 1_000_000_000) {
                    temp[flights[j][1]] = Math.min(temp[flights[j][1]], dist[flights[j][0]] + flights[j][2]);
                }
            }

            // 이번 라운드에서 딱 한 칸만 전파된 결과로 업데이트
            dist = temp;
        }

        if(dist[dst] == 1_000_000_000) return -1;
        return dist[dst];
    }
}