[GDG - 스터디] 벨만포드를 이용한 최단 경로 찾기

벨만-포드

벨만-포드(Bellman-Ford) ?

• 벨만포드 알고리즘은 그래프에서의 단일 출발지 최단 경로 문제(One-To-All)를 해결하기 위한 알고리즘으로, 다익스트라 알고리즘과 달리 **음수 가중치 간선**이 포함된 그래프에서도 사용할 수 있다.

<aside> 💡

경로 탐색 방식에는 3가지가 있다 ?

• One-To-One: 한 지점에서 다른 특정 지점까지의 최단 경로 구하기
• One-To-All: 한 지점에서 다른 모든 지점까지의 최단 경로 구하기
• All-To-All: 모든 지점에서 다른 모든 지점까지의 최단 경로 구하기 </aside>
• 다만, 음수 사이클이 있는 경우에는 최단 경로를 계산할 수 없으며, 이를 탐지하는 기능도 포함되어 있다.

---

💡 핵심 개념 - 단계별 Relaxation

• 각 간선을 반복적으로 확인하며, 시작 정점에서 다른 정점까지의 최소 비용을 점진적으로 업데이트한다.
• 한 정점에서 다른 정점으로 이동하는 최소 비용은 최대 V(정점 개수)-1번만큼의 반복으로 구할 수 있다.

---

💡 핵심 개념 - 음수 사이클 탐지

• 벨만-포드 알고리즘은 한 노드에서 다른 노드까지의 최단 경로를 많아봐야 V-1개의 간선을 지난다는 가정을 세운다. → 최단 경로가 V-1개보다 많은 간선을 지나게 된다면 음의 사이클이 존재한다는 의미이다 !
• V-1번의 간선 완화를 모두 완료한 후에도 최소 비용이 줄어드는 간선이 있다면, 즉 최단 경로가 갱신된다면 그래프에 **음수 사이클**이 존재한다고 판단한다.

---

💡 벨만 포드 - 구현

• 시간 복잡도: $O(V \times E) (정점 V, 간선 E)$
• 구현 단계
  1. 시작 정점에서 다른 모든 정점까지의 거리를 INF로 초기화하고, 시작 정점의 거리는 0으로 설정.
  2. 모든 간선을 V-1번 반복하여 확인한다.
  3. V-1번 반복후, 다시 모든 간선을 확인하여 거리가 줄어드는 간선이 있다면 음수 사이클이 존재하는 것이다.

import java.util.Arrays;

public class BellmanFord {
    static class Edge {
        int src, dest, weight;
        Edge(int src, int dest, int weight) {
            this.src = src;
            this.dest = dest;
            this.weight = weight;
        }
    }

    public static void bellmanFord(int vertices, int edges, Edge[] edgeList, int start) {
        // 최단 거리 배열 초기화
        int[] distance = new int[vertices];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[start] = 0;

        // (V-1)번 간선 완화 반복
        for (int i = 0; i < vertices - 1; i++) {
            for (Edge edge : edgeList) {
                if (distance[edge.src] != Integer.MAX_VALUE &&
                        distance[edge.src] + edge.weight < distance[edge.dest]) {
                    distance[edge.dest] = distance[edge.src] + edge.weight;
                }
            }
        }

        // 음수 사이클 확인
        for (Edge edge : edgeList) {
            if (distance[edge.src] != Integer.MAX_VALUE &&
                    distance[edge.src] + edge.weight < distance[edge.dest]) {
                System.out.println("음수 사이클이 존재합니다.");
                return;
            }
        }

        // 최단 거리 출력
        System.out.println("정점당 최단 거리:");
        for (int i = 0; i < vertices; i++) {
            System.out.println("정점 " + i + ": " + (distance[i] == Integer.MAX_VALUE ? "INF" : distance[i]));
        }
    }

    public static void main(String[] args) {
        int vertices = 5; // 정점 개수
        int edges = 8;    // 간선 개수

        // 간선 리스트 (src, dest, weight)
        Edge[] edgeList = {
            new Edge(0, 1, -1),
            new Edge(0, 2, 4),
            new Edge(1, 2, 3),
            new Edge(1, 3, 2),
            new Edge(1, 4, 2),
            new Edge(3, 2, 5),
            new Edge(3, 1, 1),
            new Edge(4, 3, -3)
        };

        // 벨만포드 알고리즘 실행
        bellmanFord(vertices, edges, edgeList, 0);
    }
}

---

문제: 타임머신 (백준 11657)

문제 링크

 

---

알고리즘 [접근 방법]

1. 벨만-포드 알고리즘을 사용하여 1번 도시에서 출발해 나머지 도시로 가는 가장 빠른 시간을 구하고 순서대로 출력한다.
2. 만약 음수 사이클이 발견된다면 해당 도시로 가는 과정에서 무한히 오래 전으로 되돌릴 수 있으므로 첫째줄에 -1을 출력한다.
3. 해당 도시로 가는 경로가 없는 경우에도 -1을 출력한다.

---

해결 코드

• V = 500, E = 6000인 경우에 최대 300만번의 반복문을 돌게 되기 때문에, 음의 간선의 가중치가 -10,000이라면 약 -300억 값으로 UnderFlow가 발생해 출력 초과가 발생하니 최단 거리 배열 dist의 자료형을 int로 하지 않도록 주의하자 !

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

public class Main {

    static final int INF = Integer.MAX_VALUE;
    static List<Edge> edgeList;
    static long[] dist;
    static boolean isMinusCycle;
    static int V, E;

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());

        edgeList = new ArrayList<>();

        // 간선 정보 입력 및 초기화
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int src = Integer.parseInt(st.nextToken());
            int dest = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            edgeList.add(new Edge(src, dest, weight));
        }

        // 벨만포드 실행
        bellmanFord();

        // 음수 사이클이 있는 경우 바로 종료
        if (isMinusCycle) {
            System.out.println("-1");
        } else {
            // 최단 거리 출력
            StringBuilder sb = new StringBuilder();
            for (int i = 2; i <= V; i++) {
                sb.append(dist[i] == INF ? "-1" : dist[i]).append("\\n");
            }
            System.out.print(sb.toString());
        }

        br.close();
    }

    static class Edge {
        int src, dest, weight;
        Edge(int src, int dest, int weight) {
            this.src = src;
            this.dest = dest;
            this.weight = weight;
        }
    }

    public static void bellmanFord() {
        // 최단 거리 배열 초기화
        dist = new long[V + 1];
        Arrays.fill(dist, INF);
        dist[1] = 0;

        // (V-1)번 간선 완화 반복
        for (int i = 0; i < V - 1; i++) {
            for (Edge edge : edgeList) {
                if (dist[edge.src] != INF &&
                        dist[edge.src] + edge.weight < dist[edge.dest]) {
                    dist[edge.dest] = dist[edge.src] + edge.weight;
                }
            }
        }

        // 음수 사이클 확인
        for (Edge edge : edgeList) {
            if (dist[edge.src] != INF &&
                    dist[edge.src] + edge.weight < dist[edge.dest]) {
                isMinusCycle = true;
                return;
            }
        }
    }
}

---

정리

• 벨만-포드 알고리즘은 특**정 시작점에서 다른 모든 노드들까지의 최단 경로(One-To-All)**를 찾는 알고리즘으로, 음수 가중치가 있는 간선을 허용하지만 음수 사이클이 있는 경우엔 이를 잡아내는 로직을 담고 있다.

 

https://thin-azimuth-2a9.notion.site/GDG-147f4ee21c00803a8149d5ed4cbb35fd?pvs=4

GDG 스터디 - 벨만포드를 이용한 최단 경로 찾기 | Notion