벨만 포드 알고리즘 : 비용이 음수인 간선이 있을 때 최단 경로 계산

모든 간선의 비용이 양수일 때는 다익스트라 최단 경로 알고리즘을 사용하면 된다. 하지만 음수 간선이 포함된다면?

 

음수 간선이 있는 경우

• 음수 간선 순환이 없는 경우
• 음수 간선 순환이 있는 경우

벨만 포드 알고리즘은 음수 간선의 순환을 감지할 수 있으며 음의 간선이 포함된 상황에서 사용할 수 있다. 시간복잡도는O(VE)로 다익스트라 알고리즘에 비해 느리다.

동작과정

1. 출발 노드 설정
2. 최단 거리 테이블 초기화
3. V-1번 반복
    3-1. 전체 간선 E개를 하나씩 확인
    3-2. 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신
4. 음수 간선 순환이 발생하는지 체크하고 싶다면 3번의 과정을 한 번 더 수행 → 최단 거리 테이블이 갱신된다면 음수 간선 순환이 존재

다익스트라 vs 벨만 포드

• 다익스트라 알고리즘 : 매번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택
• 벨만 포드 알고리즘 : 매번 모든 간선을 전부 확인. 시간은 오래 걸리지만 음수 간선 순환 탐지 가능

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

public class Main {
    static int n, m, INF = (int) 1e9;
    static ArrayList<Edge> graph;
    static int[] d;

    static class Edge {
        int v;
        int w;
        int cost;

        public Edge(int v, int w, int cost) {
            this.v = v;
            this.w = w;
            this.cost = cost;
        }
    }

    public static boolean BellmanFord(int start) {
        d[start] = 0;

        // 정점의 개수만큼 반복
        for (int i = 0; i < n; i++) {
            // 간선의 개수만큼 반복
            for (int j = 0; j < m; j++) {
                Edge edge = graph.get(j);

                // 현재 간선의 들어오는 정점에 대해 비교
                if (d[edge.v] != INF && d[edge.w] > d[edge.v] + edge.cost)
                    d[edge.w] = d[edge.v] + edge.cost;
            }
        }

        // 음의 가중치 확인
        for (int i = 0; i < m; i++) {
            Edge edge = graph.get(i); // 현재 간선

            // 현재 간선의 들어오는 정점에 대해 비교 => 더 작은 값이 생기면 음수 사이클 존재
            if (d[edge.v] != INF && d[edge.w] > d[edge.v] + edge.cost)
                return false;
        }

        return true;

    }

}