[Java] 벨만 포드(Bellman-Ford Algorithm)

서정범·2023년 3월 13일

algorithm search

자료구조와 알고리즘

목록 보기

9/30

벨만-포드 알고리즘

벨만-포드 알고리즘이란?

다익스트라 알고리즘과 같이 최단 경로(Shortest Path)를 찾는 대표적인 기법 가운데 하나인 벨만 포드 알고리즘에 대해서 정리하겠습니다.

벨만 포드 알고리즘도 다익스트라 알고리즘과 동일하게 다이나믹 프로그래밍 기법이 적용되어 있습니다.

최단경로를 구하는 것에 있어서 중요한 개념은 “최단경로의 부분 경로는 역시 최단경로이다.”라는 개념입니다.

시작노드 s에서 v에 이르는 최단경로는 s에서 u까지의 최단경로에 u에서 v 사이의 가중치(거리)를 더한 값이라는 겁니다.

D(s,v)=D(s,u)+w(u,v)

즉, 벨만-포드 알고리즘은 노드 s, u 사이의 최단 경로를 구할 때 그래프 내 모든 엣지에 대해서 경로 사이 가중치 초기화(edge relaxtion)를 수행해 줍니다. 최악의 경우 모든 노드를 다 거쳐 가야 최단 경로가 나오는 경우도 고려하여, 알고리즘은 모든 엣지에 대한 edge-relaxation을 |V| - 1회 수행합니다.

만약, V번째 edge-relaxation에서 최단 거리 값에 변화가 있으면 음의 사이클이 존재하는 그래프

동작 과정

출발 노드를 설정한다.(to, from, cost)
최단 거리 테이블을 초기화합니다. (dist[] : 최단 거리 테이블)
다음의 과정을 V - 1번 반복합니다.
1. 전체 간선 E개를 하나씩 확인합니다.
2. 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신합니다.
V번째 조회: 만약 V번째에서도 최단 거리 테이블이 갱신이 된다면 음의 사이클이 존재하는 것입니다.

특징

동적 계획법 사용, relaxtion 기법

음수 사이클 유무 확인 가능(음수 가중치 허용)

장단점

장점

음의 가중치가 있어도 최단 경로를 구할 수 있다.(음의 사이클 확인 가능)

단점

다익스트라 알고리즘보다 오랜 시간이 소모된다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

/*
* 5 9
* 4
* 1 2 10
* 1 3 5
* 2 3 2
* 3 1 1
* 3 2 13
* 4 1 8
* 4 5 3
* 5 4 9
* 5 2 31
* 출력결과
* 8 18 13 0 3
* */

/*
 * 음수 사이클있는 그래프
 * 입력
 * 5 9
 * 4
 * 1 2 -10
 * 1 3 5
 * 2 3 2
 * 3 1 1
 * 3 2 13
 * 4 1 8
 * 4 5 3
 * 5 4 9
 * 5 2 31
 * 출력 결과
 * 음수 사이클 존재
 * */
public class Main {
  static class Edge {
    int v;
    int w;
    int cost;

    Edge (int v, int w, int cost) {
      this.v = v; // 나가는 정점
      this.w = w; // 들어오는 정점
      this.cost = cost;
    }
  }
  static ArrayList<Edge> graph;

  // 정점의 개수, 간선의 개수, 출발지
  static boolean BellmanFord(int n, int m, int start) {
    int[] dist = new int[n + 1];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[start] = 0;

    // (|V| - 1개)만큼 반복
    // v와 w 사이의 최단 경로는 s와 v일 뿐일수 있고, w를 제외한 그래프의 모든 노드 (|V| - 1개)가 v, w 사이의 최단경로를 구성할 수도 있습니다.
    // 즉, edge-relaxation을 |V|회 만큼 실행 했을 때, 최단 거리가 수정된다는 것은 음수 사이클을 돈다는 것을 의미한다.
    for (int i = 0; i < n - 1; i++) {
      // 간선의 개수만큼 반복
      for (int j = 0; j < m; j++) {
        Edge edge = graph.get(j);

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

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

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

    //출력
    for (int i = 1; i < dist.length; i++) {
      if (dist[i] == Integer.MAX_VALUE) {
        System.out.print("INF ");
      } else
        System.out.print(dist[i] + " ");
    }
    return true;
  }

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

    // 그래프 입력받기
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());

    graph = new ArrayList<>();

    for (int i = 0; i < m; i++) {
      st = new StringTokenizer(br.readLine());
      int v = Integer.parseInt(st.nextToken());
      int w = Integer.parseInt(st.nextToken());
      int cost = Integer.parseInt(st.nextToken());

      graph.add(new Edge(v, w, cost));
    }

    BellmanFord(n, m, 4);
  }
}