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

💡 벨만-포드(Bellman-ford)는 그래프에서 음수 가중치 간선이 있을 때 최단 거리를 구하는 알고리즘이다.

 

• 다익스트라(Dikjstra), 플로이드-워셜(Floyd-Warshall) 알고리즘과 함께 그래프의 최단 거리를 구하는 방법이다.
• 위 알고리즘들과 다르게 음수 가중치의 간선이 있어도 최단 경로를 구할 수 있다.
• 단, 음수 사이클이 있을 경우 최단 거리를 구할 수 없으므로 예외 처리가 필요하다.
  (음수 사이클의 존재 여부를 파악할 수 있다).
• 매번 모든 간선을 확인하기 때문에 시간 복잡도는 O(VE) = Vertex * Edge로 다익스트라보다 느리다.

 

🚀 벨만-포드 알고리즘 동작 과정

• 출발노드, 도착노드, 가중치 3개의 변수를 갖은 Edge클래스(혹은 배열)를 선언한다.
• 계산 결과인 최단경로를 저장할 배열 dist를 선언하고, 시작 노드는 0, 나머지는 무한대로 초기화한다.
• 최단거리 리스트에서 업데이트 반복 횟수는 (전체 노드 개수) -1번이다.
  ( 시작 노드에서 N - 1개의 간선이면 모든 노드를 갈 수 있다 )
• 모든 간선을 확인해서 dist[도착 노드] > dist[현재 노드] + [가중치] 인 경우, dist[도착 노드]를 업데이트한다.
• 음수 사이클을 확인하기 위한 방법으로 N-1번의 반복 이후 한번 더 계산한다.
  이때 dist 배열이 업데이트되면 음수 사이클이 있는 경우이므로 최단 거리를 구할 수 없다.
  (반복 시 무한히 최단 거리가 작아지기 때문)

 

🚀 벨만-포드 알고리즘의 핵심코드

if(dist[출발 노드] == 무한대){
	continue;
}
if(dist[도착 노드] > dist[출발 노드] + 간선 가중치 ){
	dist[도착 노드] = dist[출발 노드] + 간선 가중치;
}

 

• 출발 노드의 최단 거리가 무한대인 경우는 아직 방문하지 않았다는 것이므로 제외한다.
• 최단 거리 배열 dist를 N-1번 업데이트한다.
• 마지막 N번째 한번 더 업데이트해서 음수 사이클을 확인한다.

 

🚀 벨만-포드 알고리즘 예제  코드

백준 11657 타임머신 문제 풀이 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        // Input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        long[] dist = new long[N + 1];
        Edge[] edges = new Edge[M];

        for (int i = 1; i <= N; i++) {
            dist[i] = Integer.MAX_VALUE;
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            edges[i] = new Edge(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }

        // Bellman-ford-moore
        dist[1] = 0;
        boolean minusCircle = false;
        for (int i = 1; i <= N; i++) {
            for (int j = 0; j < M; j++) {
                if (dist[edges[j].start] == Integer.MAX_VALUE) // 엣지 시작 노드가 방문 전(무한대)이면 통과
                    continue;
                if (dist[edges[j].end] > dist[edges[j].start] + edges[j].cost) {
                    dist[edges[j].end] = dist[edges[j].start] + edges[j].cost;
                    if (i == N) {
                        minusCircle = true;
                    }
                }
            }
        }

        // Output
        if (minusCircle)
            bw.write("-1");
        else {
            StringBuilder sb = new StringBuilder();
            for (int i = 2; i <= N; i++) {
                if (dist[i] == Integer.MAX_VALUE)
                    sb.append("-1");
                else
                    sb.append(dist[i]);
                sb.append('\n');
            }
            bw.write(sb.toString().stripTrailing());
        }
        bw.flush();
    }

    private static class Edge {
        int start, end, cost;

        public Edge(int start, int end, int cost) {
            this.start = start;
            this.end = end;
            this.cost = cost;
        }
    }
}

 

🚀 참고

• https://innovation123.tistory.com/132
• https://velog.io/@changhee09/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%B5%9C%EB%8B%A8%EA%B2%BD%EB%A1%9C-%EB%B2%A8%EB%A7%8C-%ED%8F%AC%EB%93%9C

 

🚀 관련 문제 풀이

• [G4] BOJ_11657 : 타임머신 (24.05.10)