[고급 알고리즘] Graph(Shortest Path): Bellman-Ford

1. Bellman-Ford

• 가중 유향 그래프에서 최단 경로 문제를 푸는 알고리즘
• 단일 출발점에서 모든 정점까지의 최단 거리를 구함
• ✅ 음수 간선 허용
• ✅ 음수 사이클 판별 가능

 

2. 동작 원리

• 정점의 갯수 - 1 번 완화를 반복 수행함
• ➡️ 최종적으로 출발지에서 모든 정점까지의 최단 거리를 구할 수 있음

 

초기화

• ✅ 자기 자신으로 가는 최단 거리 = 0
• ✅ 다른 정점으로 가는 최단 거리 = INF (도착 못함)

 

간선 완화

• 최대 간선 수 = 정점의 갯수-1 (사이클이 일어나지 않는다는 가정)
• ✅ 점점 최단거리가 갱신됨

 

음수 사이클 검사

• 사이클을 한 바퀴 돌 때마다 전체 비용이 계속 줄어드는 사이클
• ✅ 사이클을 많이 돌수록 총 가중치는 무한히 작아짐
• ✅ 즉, 최단경로가 없다 볼 수 있음
• ➡️ 모든 간선에 대해서 간선의 도착지로 가는 비용이 간선의 시작지로 가는 비용 + 가중치보다 큰지 확인하여 판별함

 

3. 구현

import java.io.*;
import java.util.*;

public class Main {
    
    private static StringBuilder sb = new StringBuilder();
    private static int n, m, INF = Integer.MAX_VALUE;
    private static Edge[] edges;
    private static long[] dists;
    
    public static void main(String... args) throws IOException {
        n = readInt();
        m = readInt();
        
        edges = new Edge[m];
        for (int i = 0; i < m; i++) edges[i] = new Edge(readInt(), readInt(), readInt());
        
        dists = new long[n];
        Arrays.fill(dists, INF);
        dists[0] = 0;
        
        for (int i = 0; i < n-1; i++) {
            boolean updated = false;
            for (Edge edge : edges) {
                if (dists[edge.s] == INF) continue;
                long nd = dists[edge.s] + edge.w;
                if (nd < dists[edge.d]) {
                    dists[edge.d] = nd;
                    updated = true;
                }
            }
            
            if (!updated) break;
        }
        
        for (Edge edge : edges) {
            if (dists[edge.s] == INF) continue;
            if (dists[edge.s] + edge.w < dists[edge.d]) {
                System.out.println(-1); // ⚠️ 음수 사이클
                return;
            }
        }
        for (int i = 1; i < n; i++) sb.append(dists[i] == INF ? -1 : dists[i]).append("\n");
        
        System.out.print(sb);
    }
    
    static class Edge {
        int s, d, w;
        Edge(int s, int d, int w) {
            this.s = s;
            this.d = d;
            this.w = w;
        }
    }
}

Time Complexity: O(V+E)

 

출처

• Wiki - 벨먼-포드 알고리즘