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

1. 벨만포드(Bellman-Ford) 알고리즘이란?

• 한 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘 + 음수 사이클 존재 여부를 알 수 있음
• 다익스트라와는 달리 가중치에 음수가 있어도 사용 가능
• 시간복잡도: O(NE) (N:노드의 수, E:엣지의 수)

• 다음과 같은 그래프가 있다고 가정
• 다익스트라로 노드 1에서 모든 노드로의 거리를 구하면
• 1 -> 2 = 1
• 1 -> 2 ->3 = 2
• 1-> 2 ->3 ->4 = 4 가 되고
• 노드 2는 이미 방문했기 때문에 4 ->2 경로는 고려하지 않음
• 결과적으로 1 -> 2의 최단경로는 1이 됨
• 하지만 실제 1 -> 2의 최단경로는 -∞ 임
• 이를 해결하기 위해 벨만포드 알고리즘 탄생

 

2. 알고리즘 동작 원리

• 시작 정점을 선택한다.
• 모든 간선들을 탐색하면서, 시작 정점에서 다른 정점까지의 거리가 INF가 아니라면 거리를 갱신한다. 이 과정을 (정점의 수 -1)번만큼 진행한다.
• 마지막으로 2번을 수행한다.

2번 과정에서 (정점의 수-1)번 만큼 진행하는 이유는 V개의 정점과 E개의 간선이 있는 가중 그래프에서 정점 A에서 정점 B까지의 최단 거리는 최대 V-1개의 정점을 지나기 때문이다.

 

V-1개 이상의 정점을 방문하는 것은 결국 중복 방문을 하는 것이기 때문에 최단 경로가 성립될 수 없다.

 

또한, 3번 과정에서 마지막으로 2번 과정을 한 번 더 수행하는 이유는 음의 사이클 유무를 판단하기 위해서이다. 만약 V 개의 정점을 지났는데 최단 경로가 갱신이 된다면 음의 사이클이 발생한 것이며 비용이 무한하게 갱신이 되기 때문에 최단 경로를 구할 수 없다.

 

그림과 함께 알아보자.

---

1. 초기화

출발지(시작 노드)를 제외한 모든 노드로의 최단 거리를 무한대로 초기화한다. 출발지의 거리는 0이다.

 

2. 최단거리 계산

V-1번 동안 모든 엣지를 확인한다.

현재 엣지의 도착지점에 저장된 최단 거리보다 현재 엣지까지의 최단 거리 + 현재 엣지의 거리가 짧을 경우 최단 거리를 갱신한다.

for(i=1; i<V; i++) // V-1번
	for(Edge now : EdgeList) // 모든 엣지에 대해
		if(distance[now.end] > dist[now.start] + now.cost)
			distance[now.end] = dist[now.start] + now.cost

이때, 엣지의 출발지가 무한대인 경우엔 갱신이 되지 않기 때문에 첫 번째 탐색에서는 시작 정점과 이어진 엣지만 갱신이 발생한다.

즉, 첫 번째 탐색에서 엣지가 최대 하나 포함된 최단 거리가 구해진다.

 

두 번째에서는 거기에 하나 더 나아갈 수 있게 되므로 최대 두 개의 엣지가 포함된 최단 거리가 구해진다.

 

따라서 i번째 탐색에 i개의 엣지가 포함된 최단 거리가 구해지고, 경로에는 사이클이 생기면 안 되기 때문에 최단 거리 탐색은 V-1번으로 끝난다.

 

3. V번째 탐색 - 확인 과정

V-1번에서 최단 거리 탐색이 끝나기 때문에 더이상 탐색을 진행해도 갱신이 발생해서는 안 된다.

V번째에 갱신이 발생한다 → 음수 사이클이 존재한다.

for(Edge now : EdgeList)
	if(distance[now.end] > dist[now.start] + now.cost)
		return false // 음수 사이클 존재
return true

---

예시문제풀이

https://www.acmicpc.net/problem/11657

문제

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다.

1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다.

 

출력

만약 1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래 전으로 되돌릴 수 있다면 첫째 줄에 -1을 출력한다. 그렇지 않다면 N-1개 줄에 걸쳐 각 줄에 1번 도시에서 출발해 2번 도시, 3번 도시, ..., N번 도시로 가는 가장 빠른 시간을 순서대로 출력한다. 만약 해당 도시로 가는 경로가 없다면 대신 -1을 출력한다.

 

public class Main {
    static int N;
    static int M;
    static List<Node> graph;
    static int INF = Integer.MAX_VALUE;
    static long[] dist;

    static class Node {
        int start;
        int end;
        int time;

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

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        graph = new ArrayList<>();
        dist = new long[N+1];
        Arrays.fill(dist, INF);
        dist[1] = 0; // 출발지는 0으로

        for(int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int time = Integer.parseInt(st.nextToken());
            graph.add(new Node(start, end, time));
        }

        if(bellmanFord()) System.out.println(-1);
        else {
            StringBuilder sb = new StringBuilder();
            for(int i = 2; i<=N; i++) {
                if(dist[i]==INF) sb.append(-1);
                else sb.append(dist[i]);
                sb.append("\n");
            }
            System.out.println(sb);
        }
    }

    static boolean bellmanFord() {
        /* 1. 최단거리 계산 */
        for(int i = 1; i <= M; i++) {
            for(Node node : graph) {
                if(dist[node.start] != INF && dist[node.end] > dist[node.start] + node.time) { // 갱신
                    if(i == M)  return true; // 2. 사이클 발생 여부 체크
                    dist[node.end] = dist[node.start] + node.time;
                }
            }
        }

        return false;
    }
}

 

 

 

📗참고사이트

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