[알고리즘] 벨만-포드 (Feat. 최단 경로)

Intro

어떤 정점으로부터 모든 정점들로의 최단 경로를 구하는 문제는 최단 경로 알고리즘을 적용해서 정해를 구할 수 있다.

이 때 사용되는 최단 경로 알고리즘으로는 아래와 같다.

• 다익스트라(Dijkstra) 알고리즘
• 벨만-포드(Bellman-Ford) 알고리즘
• 플로이드-워셜(Floyd-Warshall) 알고리즘

아래 표는 최단 경로 알고리즘 3가지의 각 차이점에 대해 참고할 수 있도록 생성형 AI를 통해 생성한 자료

구분	다익스트라(Dijkstra)	벨만-포드(Bellman-Ford)	플로이드-워셜(Floyd-Warshall)
목적	단일 출발점에서 다른 모든 정점까지의 최단 거리	단일 출발점에서 다른 모든 정점까지의 최단 거리	모든 정점 쌍 간 최단 거리
음수 가중치	❌ 불가능 (음수 간선 있으면 오동작)	✅ 가능	✅ 가능
음수 사이클 탐지	❌ 불가능	✅ 가능	✅ 가능 (응용 가능)
시간 복잡도	O(E log V) (우선순위 큐 사용 시)	O(VE)	O(V³)
공간 복잡도	O(V + E)	O(V + E)	O(V²)
그래프 유형	가중치가 양수인 방향/무방향 그래프	방향 그래프 (음수 간선 가능)	방향 그래프 (모든 쌍)
사용 예시	네비게이션, 네트워크 라우팅	환율 계산, 음수 사이클 탐지	경로 테이블 계산, 전체 최단 거리 미리 계산

 

각 알고리즘에 대해 세부적인 원리에 대해 개별 포스팅으로 정리해보기로 하고, 이번 포스팅에서는 벨만-포드 알고리즘에 대해 작성해보려한다.

INDEX

다익스트라(Dijkstra) 알고리즘 포스팅

벨만-포드(Bellman-Ford) 알고리즘 포스팅 (현재)

플로이드-워셜(Floyd-Warshall) 알고리즘 포스팅

 

---

Concept

벨만-포드 알고리즘의 경우 다익스트라와 동일하게 단일 출발점에서부터 모든 정점으로의 최단 경로를 구하는 알고리즘이다.

중요한 차이점으로는 다익스트라와 달리 '음수'를 구분할 수 있다. 음수 가중치가 들어와도 상관없으며, 사이클 또한 판단이 가능하다.

플로이드 워셜도 마찬가지로 '음수'에 대해서 구분이 가능하지만 시간복잡도 측면에서 큰 차이가 나기 때문에 참고해두면 좋을것같다.

 

마지막 부분에는 다익스트라로는 풀리지 않는 문제들을 추천할 예정이니 참고하여 풀어보면서 '음수'라는 차이점에 대해 알아갈 수 있으면 좋을듯 하다.

 

동작 원리

---

먼저 다익스트라가 왜 음수 간선 및 사이클을 구분할 수 없는지에 대해 알아두면 좋다.

먼저 위와 같은 그래프가 있다고 가정해보자.

다익스트라를 통해 1번에서 3번까지의 최단 경로를 구하게 되면 어떤 값이 나오게 될까?

육안으로 확인했을 때는 간단하게 1 -> 2 -> 3 번 경로인 '5'가 최단 경로가 되는것을 쉽게 알 수 있다.

그러나 다익스트라를 돌려보면 5가 아닌 10이라는 값을 확인할 수 있다.

 

그 이유는 다익스트라의 주요 코드 조각을 보면 알 수 있다.

for(Node nxt : list.get(cur.v)) {
    int nxtDist = cur.time + nxt.time;
    if(nxtDist < dist[nxt.v]) {
        dist[nxt.v] = nxtDist;
        pq.offer(new Node(nxt.v, nxtDist));
    }
}

다익스트라의 경우 현재 정점을 기준으로 연결된 모든 간선들을 확인함과 동시에 최단경로 배열 dist를 갱신해주고 있다.

1번 정점에서 볼 땐, 1 -> 2로 가는 30보다는 1 -> 3으로 가는 10이 최단 경로이기 때문에 dist[3]을 10으로 갱신한다.

그 후에 1 -> 2로 연결된 간선에서는 dist[3]보다 크기 때문에 탐색을 하지 않는다. (물론 간선의 순서에 영향을 받을 수 있겠지만 안되는 경우가 있다는것에 주의하자.)

---

이처럼 다익스트라는 특정 정점으로 가는 경로에 음수 간선이 존재할 경우 정해가 구해지지 않는 경우가 존재한다.

그럼 이제 벨만-포드는 어떤 점이 다르며, 음수에 대해 어떻게 처리하는지 보도록 하자.

 

먼저 큰 차이로는 다익스트라의 경우 현재 정점을 기준으로 탐색을 진행하지만, 벨만-포드의 경우 간선을 기준으로 탐색을 진행하게 된다. 즉 위 그래프에서 '10', '30', '-25' 라는 간선을 기준으로 dist 배열을 갱신하게 된다.

그렇기에 탐색을 하지않는 경우가 없이 모든 경우의 수를 탐색하게 된다.

 

해당 알고리즘에 대해 한줄 요약(?)을 한다면 아래가 될 것 같다.

"단방향 간선을 기준으로 start정점까지의 경로가 기존에 존재한다면 이 값을 활용해서 end정점까지의 경로를 비교한다."

 

좀 더 자세히 알아보기 위해 위 그래프를 기준으로 과정에 대해 상세히 나열해보겠다.

 

우선 첫번째 간선(start : 1, end : 3, weight : 10)에서는 아래와 같이 진행이 된다.

dist[1]이 INF(무한값)이 아니라면 1번까지의 경로는 존재함을 의미한다. (1번에서 출발한다고 가정 dist[1] = 0)

3번으로의 최단경로를 갱신할 수 있는데 dist[1] + weight(10)이 dist[3]보다 낮다면 갱신한다.

 

갱신후의 dist 배열은 아래와 같다.

dist[1]	dist[2]	dist[3]
0	INF	10

 

그럼 이제 다음 간선(start : 1, end : 2, weight : 30)에 대해 보도록 하자.

해당 간선도 마찬가지로 dist[1]이 INF가 아니기 때문에 최단경로 탐색이 가능하다.

dist[2]의 경우 INF이며, 갱신할 값은 dist[1] + weigth값인 30이 된다. 따라서 갱신후의 dist 배열은 아래와 같다.

dist[1]	dist[2]	dist[3]
0	30	10

 

이제 마지막 간선(start : 2, end : 3, weight : -25)에서 어떻게 갱신이 이루어질까?

이전 간선에서 dist[2]는 갱신이 되어 INF가 아니기에 탐색이 가능하다.

또한 dist[2] + weight값인 5는 dist[3]보다 낮기 때문에 갱신이 되어 dist 배열은 아래와 같이 변경된다.

dist[1]	dist[2]	dist[3]
0	30	5

---

여기까지 봤을 때는 간선들에 대해 한번의 반복으로 원하는 최단경로가 구해진 것 처럼 보인다.

그러나 한가지 궁금증이 생기게 될 텐데, 간선의 순서가 변경이 되어 dist[2]가 갱신되기 전에 2 -> 3 간선을 보게될 경우에는 제대로 된 갱신이 안되는 것 아닌가 하는 궁금증이다.

이 부분에 대한 답은 간단하다. 이러한 반복을 정점의 개수만큼 반복하면 된다.

정점의 개수만큼만 반복하면 되는 이유는 "단순 경로는 최대 V-1개의 간선만 포함할 수 있기에, 해당 수만큼만 반복하면 모든 가능한 최단 경로가 계산되기 때문"이다.

첫번째 반복에서는 한개의 경로를 사용한 각 정점으로의 최단 경로가 계산된다.

두번째 반복에서는 이전에 한개의 경로를 사용했던 최단 경로에서 추가로 한개의 경로를 더 사용한 최단 경로가 계산된다.

...

이런식으로 V-1번의 반복이 이루어지면 모든 경로를 활용한 최단 경로가 구해지게 된다.

 

음수 사이클 판단

음수 사이클이 존재하는지 판단하는건 간단하다.

위에서 언급한것과 같이 V-1번 반복을 하게되면 모든 간선을 포함한 최단 경로를 구할 수 있다고 했다.

"그 말은 V번째 반복에서 갱신이 되는 정점이 존재한다면?"

음수 사이클이 존재하는 경우다.

 

정말 간단하기에 아래 코드 구현에서 참고하면 좋을듯 하다.

---

Implement

초기화

[입력 부분]

보통 그래프 문제에서는 인접리스트를 사용하여 간선의 정보를 초기화하게 되는데, 벨만-포드의 경우 간선을 기준으로 순회를 하기 때문에 간선에 대한 리스트로 초기화하여 사용하는게 편하다.

n = Integer.parseInt(st.nextToken());   //정점 수
m = Integer.parseInt(st.nextToken());   //간선 수

List<Node> list = new ArrayList<>();

for(int i=0; i<m; i++) {
    st = new StringTokenizer(br.readLine());
    int start = Integer.parseInt(st.nextToken());
    int end = Integer.parseInt(st.nextToken());
    int weight = Integer.parseInt(st.nextToken());
    list.add(new Node(start, end, weight));
}

 

[거리 배열]

dist배열의 경우는 다익스트라와 동일하다. 각 정점에 대해 INF값으로 초기화 후 시작 정점에 대해서만 0으로 변경해주면 된다.

dist = new long[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist['시작정점'] = 0;

포인트는 long 자료형을 사용한 부분인데, 음수 간선까지 포함하여 탐색을 하다보면 뜻하지않게 계속해서 갱신이 되는 경우가 있는데, 이 때문에 오버플로우가 날 수 있다. 웬만하면 long을 사용하여 오버플로우를 방지하는게 좋을듯 하다.

 

주요 코드 조각

for(int i=1; i<=n; i++) {	//정점 수만큼 반복
    for(int j=0; j<m; j++) {
        Node cur = list.get(j); //j번째 간선

        if(dist[cur.start] != Integer.MAX_VALUE && dist[cur.end] > dist[cur.start] + cur.time) {
            dist[cur.end] = dist[cur.start] + cur.time;
        }
    }
}

//음수 사이클 판단
for(int i=0; i<m; i++) {
    Node cur = list.get(i);

    if(dist[cur.start] != Integer.MAX_VALUE && dist[cur.end] > dist[cur.start] + cur.time) {
        return false;
    }
}

첫번째 이중 반복문이 벨만-포드 알고리즘의 주요 코드다.

간선 수만큼 반복을 하며 최단 경로를 갱신한다. 이 과정을 최소 V-1 이상 반복한다. (더 반복하는건 상관없다)

 

갱신 조건문은 아래와 같다.

1. 현재 간선을 기준으로 start정점까지의 경로가 존재해야 한다. (dist[cur.start] != Integer.MAX_VALUE)
2. end정점의 최단 경로보다 현재 경로가 더 최소가 되어야 한다. (dist[cur.end] > dist[cur.start] + cur.time)

두 조건을 만족하면 최단 경로 갱신이 이루어진다.

 

아래에 있는 음수 사이클판단의 경우 한번 더 간선 순회를 하면서 갱신이 이루어지는 정점이 있는지 찾는 부분이다.

만약 갱신이 이루어지는 부분이 있다면 음수 사이클이 존재하는 경우다.

 

전체 코드

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

//벨만-포드 알고리즘
public class Main {
    static class Node {
        int start;
        int end;
        int weight;
        public Node(int start, int end, int weight) {
            this.start = start;
            this.end = end;
            this.weight = weight;
        }
    }
    static int n, m;
    static List<Node> list;
    static long[] dist;
    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());   //간선 수

        list = new ArrayList<>();

        for(int i=0; i<m; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            list.add(new Node(start, end, weight));
        }

        if(BellmanFord()) {
            // 최단 경로 출력
            System.out.println(Arrays.toString(dist));
        }
        else {
            System.out.println("음수 사이클 존재");
        }

    }

    static boolean BellmanFord() {
        //방문체크 대신 dist배열 활용 전부 무한대로 초기화
        dist = new long[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[1] = 0;

        for(int i=0; i<n; i++) {    //최소 n-1번 이상만 수행한다면 상관없다.
            for(int j=0; j<m; j++) {
                Node cur = list.get(j); //j번째 간선

                if(dist[cur.start] != Integer.MAX_VALUE && dist[cur.end] > dist[cur.start] + cur.weight) {
                    dist[cur.end] = dist[cur.start] + cur.weight;
                }
            }
        }

        //음수 사이클 판단
        for(int i=0; i<m; i++) {
            Node cur = list.get(i);

            if(dist[cur.start] != Integer.MAX_VALUE && dist[cur.end] > dist[cur.start] + cur.weight) {
                return false;
            }
        }

        return true;
    }
}

---

관련 문제

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