그래프 최단 경로 알고리즘 - 벨만 포드(Bellman-Ford) 알고리즘

벨만 포드 알고리즘이란?

---

다익스트라 알고리즘과 벨만 포드 알고리즘 모두 가중치가 있는 그래프에서 최단 경로를 구하는 알고리즘이다.

하지만 벨만포드가 다익스트라에 비해 갖는 특징이 있다.

바로 위와 같은 음의 가중치가 있는 그래프에서도 작동한다는 것이다.

더불어 음의 사이클도 감지가 가능하다.

 

음의 사이클이란?

 

음의 사이클 예시

음의 사이클이란 경로의 합이 음수가 되는 사이클을 말한다.

위의 사례에 경우 B에서 C를 거쳐 다시 B로 돌아오는 사이클이 존재하는데 이 경우 -3의 비용이 발생한다. 

이렇게 되면 최단 거리가 무한대로 줄어들게 된다.

벨만포드 알고리즘은 이러한 음의 사이클까지 감지가 가능하다. 

	다익스트라	벨만 포드
음의 가중치 그래프 적용 가능	X	O
음의 사이클 감지 가능	X	O

 

정리하자면 벨만포드 알고리즘은 가중치가 있는 그래프에서 최단경로를 구하는 알고리즘이며 음의 가중치 그래프에서도 적용 가능하고 음의 사이클도 적용가능한 알고리즘이라고 할 수 있다.

 

벨만 포드 알고리즘 동작 방식

---

벨만 포드 알고리즘은 매 단계마다 모든 간선의 가중치를 다시 확인하여 최소비용을 갱신하기 때문에 음의 가중치를 가지는 그래프에서도 최단 거리를 구할 수 있다.

벨만 포드 알고리즘의 동작 방식은 다음과 같다.

 

1. 시작 노드를 정하고 테이블을 초기화한다. 테이블에는 시작 노드에서 각 노드까지의 최소 비용과 직전 노드를 저장한다. 

     1-1. 시작 노드의 경우 최소 비용을 0, 직전 노드를 자기 자신으로 초기화 한다.

     1-2. 나머지 노드의 경우 최소 비용을 무수히 큰 값, 직전 노드를 임의의 더미 값으로 초기화한다.
(이 과정은 다익스트라 알고리즘과 같음)

2. 모든 노드에 대하여 현재 노드에서 인접 노드까지의 비용을 기존 테이블의 최소비용 값과 비교해
     더 작은 경우 갱신한다. 이때 직전 노드도 현재 노드로 갱신한다

(이 과정은 모든 간선의 가중치를 확인하기 위한 과정이다.)

 3. 2번 과정을 노드 갯수 - 1번 반복한다.

 4. 이후 2번 과정을 한 번 더 수행하여 음의 사이클 발생 여부를 체크한다.

 

왜 노드 - 1번 반복할까?

ChatGPT 4o 답변

즉, 최단 경로는 최대 V-1개의 간선으로 이루어져있기 때문에 V-1번 반복한다는 소리이다.

V-1번 수행한 후 한 번 더 수행했는데 여전히 거리가 업데이트 된다면 이는 음의 가중치가 발생한다는 뜻이다.

 

그림으로 보도록하자 

 

다음과 같은 그래프가 있다고 가정해보자.

 

1. 시작 노드를 정하고 테이블을 초기화한다. 테이블에는 시작 노드에서 각 노드까지의 최소 비용과 직전 노드를 저장한다. 

시작 노드를 A로 설정한다.

 

2. 모든 노드에 대하여 시작 노드에서 인접 노드까지 가는 비용을 기존 테이블의 최소비용 값과 비교해
     더 작은 경우 갱신한다. 이때 직전 노드도 현재 노드로 갱신한다

 

1번째 반복

1) A

• B의 경우 8(0+8)이므로 기존 테이블의 INF값보다 작기 때문에 테이블의 값을 8로 업데이트 한다.
  직전 노드도 A로 업데이트 한다.
• C의 경우 10(0+8)이므로 기존 테이블의 INF값보다 작기 때문에 테이블의 값을 10으로로 업데이트 한다.
  직전 노드도 A로 업데이트 한다.

2) B

• E의 경우 9(8+1)이므로 기존 테이블의 INF값보다 작기 때문에 9로 업데이트 한다.
  직전 노드도 B로 업데이트 한다.

3) C

• F의 경우 12(10+2)이므로 기존 테이블의 INF값보다 작기 때문에 12로 업데이트 한다.
  직전 노드도 C로 업데이트 한다.

4) D

• C의 경우 INF(INF+1)이므로 기존 테이블의 10값보다 크기 때문에 업데이트 하지 않는다.

5) E

• C의 경우 5(9 + -4)이므로 기존 테이블의 INF값보다 작기 때문에 5로 업데이트 한다.
  직전 노드도 E로 업데이트 한다.
• F의 경우 8(9 + -1)이므로 기존 테이블의 12보다 작기 때문에 8로 업데이트 한다.
  직전 노드도 E로 업데이트 한다.

6) F

• D의 경우 6(8 + -2)이므로 기존 테이블의 INF값보다 작기 때문에 6으로 업데이트 한다.
  직전 노드도 F로 업데이트 한다

1회전 결과

1번째 반복이 끝났다.

이 과정을 계속 반복하면 된다.

한번만 더 해보겠다.

 

2번째 반복

1) A

• B의 경우 8(0+8)이므로 기존 테이블의 8값과 같기 때문에 업데이트 하지 않는다.
• C의 경우 10(0+10)이므로 기존 테이블의 값 5보다 크기 때문에 업데이트 하지 않는다.

2) B

• E의 경우 9(8+1)이므로 기존 테이블의 9값과 같기 때문에 업데이트 하지 않는다.

3) C

• F의 경우 7(5 + 2)이므로 기존 테이블의 8값보다 작기 때문에 7로 업데이트 한다.
  직전 노드도 C로 업데이트 한다

4) D

• C의 경우 7(6+1)이므로 기존 테이블의 5값보다 크기 때문에 업데이트 하지 않는다.

5) E

• C의 경우 5(9 + -4)이므로 기존 테이블의 5값과 같기 때문에 업데이트 하지 않는다.
• F의 경우 8(9 + -1)이므로 기존 테이블의 7값 보다 크기 때문에 업데이트 하지 않는다.

6) F

• D의 경우 5(7 + -2)이므로 기존 테이블의 6값보다 작기 때문에 5로 업데이트 한다.
  직전 노드는 그대로 F가 된다.

2회전 결과

이 과정을 3번 더 반복하면 된다.

 

3,4,5번째 반복 결과

2번째 반복에서 변화가 없다.

 

한번 더 반복해서 음의 사이클 여부 체크

역시 변화가 없기 때문에 음의 사이클은 발생하지 않는다.

 

 

벨만 포드 구현하기

---

벨만 포드를 구현할 때는 다익스트라의 우선순위큐와 같은 특별한 자료구조를 활용하지는 않는다.

그냥 단순하게 V-1번 모든 간선을 방문해서 최소 비용을 업데이트하면 된다.

그리고 한 번 더 모든 간선을 방문해 음의 사이클 여부를 알아내면 된다.

 

코딩테스트에선 최단경로를 묻는 문제보다는 최소비용을 묻는 문제가 많이 나오므로 최소비용만 구현하도록 하겠다.

 

바로 코드를 보자

import java.util.*;

public class Node {
    int vertex;
    int weight;

    public Node(int vertex, int weight) {
        this.vertex = vertex;
        this.weight = weight;
    }
}

class Graph {
    int N; // 노드의 갯수
    List<List<Node>> graph;

    Graph(int N) {
        graph = new ArrayList<>();
        for(int i = 0; i < N; i++) {
            graph.add(new ArrayList<>());
        }
    }
    public void addEdge(int src, Node node){
        graph.get(src).add(node);
    }
}

public class BellmanFord
{

    public static int[] bellman_ford(List<List<Node>> graph, int start, int n) {

        int[] distance = new int[n];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[start] = 0;

        for(int i = 0; i < n - 1; i ++) {

            for(int j = 0; j < n; j++) {
                int src = j;

                for (Node neighbor : graph.get(src)) {
                    if (distance[src] != Integer.MAX_VALUE &&
                            distance[neighbor.vertex] > neighbor.weight + distance[src]) {
                        distance[neighbor.vertex] = neighbor.weight + distance[src];
                    }
                }
            }
            System.out.println("distance = " + Arrays.toString(distance));
        }

        for(int j = 0; j < n; j++) {
            int src = j;
            List<Node> nodeList = graph.get(src);

            for(Node neighbor: nodeList) {
                if(distance[neighbor.vertex] > neighbor.weight + distance[src]) {
                    System.out.println("음의 사이클 발생!");
                    return distance;
                }
            }
        }

        System.out.println("음의 사이클 발생X!");
        return distance;
    }

    public static void main(String[] args) {

        Graph graph = new Graph(6);
        graph.addEdge(0, new Node(1, 8));
        graph.addEdge(0, new Node(2, 10));
        graph.addEdge(1, new Node(4, 1));
        graph.addEdge(2, new Node(5, 2));
        graph.addEdge(3, new Node(2, 1));
        graph.addEdge(4, new Node(2, -4));
        graph.addEdge(4, new Node(5, -1));
        graph.addEdge(5, new Node(3, -2));

        System.out.println(Arrays.toString(bellman_ford(graph.graph, 0, 6)));
    }
}

시간복잡도

• O(E * V)
  

노드 갯수 V에 대하여 V - 1번 간선 E개를 확인했으므로 O(E * (V-1))인데 상수는 무시할 수 있기 때문에 O(E * V)가 된다.

 

다익스트라 알고리즘 VS 벨만 포드 알고리즘 비교

---

	다익스트라	벨만포드
목적	가중치가 있는 그래프에서 특정 노드에서 다른 노드까지의 최단 경로 찾기	가중치가 있는 그래프에서 특정 노드에서 다른 노드까지의 최단 경로 찾기
음의 가중치 그래프 적용 가능	X	O
음의 사이클 탐지 가능	X	O
시간 복잡도	O(ElogV)	O(EV)