[알고리즘] 최단거리 알고리즘 벨만포드 Java 참고 코드

그래프가 주어졌을 때, 한 노드에서부터 다른 모든 노드들까지의 최단 거리를 구하는 것을 Single Point Shortest Path 라고 한다. Single Point Shortest Path 를 구하는 알고리즘에는 벨만포드 알고리즘 과 다익스트라 알고리즘 이 있다. 벨만포드 알고리즘은 O(V^3) 시간복잡도를 갖는다. 이는 다익스트라보다 오래 걸리는 수치다. 그러나 그래프에서 음수 가중치가 존재할 때도 사용 가능하며, 음수 사이클이 있는지 판별할 수도 있다.

알고리즘의 기본원리는 이렇다. V개의 정점과 E개의 간선으로 이루어진 그래프에서 어떤 정점 A와 B 사이의 최단경로 상에 존재하는 간선의 개수는 최대 V - 1 개이다. 따라서 시작점의 distance를 0으로 설정하고 V - 1 번 반복하면서 간선경감 이라는 연산을 하면 모든 정점에 대해서 최단 경로의 길이가 구해진다.

음수 사이클 판정은 다음과 같다. 모든 간선에 대해서 V번 간선경감을 진행한다. 음수사이클이 없다면 V - 1 번째 반복에서 모든 정점에 대한 최단 거리가 구해진다. 그러나 음수사이클이 존재한다면 V번째 반복에서도 간선경감이 일어나 어느 정점의 최단 거리를 갱신시킨다. 이 포인트를 체크해서 음수사이클 존재 여부를 판단할 수 있다.

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

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

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String[] strs = br.readLine().split(" ");
    
    int n = Integer.parseInt(strs[0]);
    int m = Integer.parseInt(strs[1]);
    
    long[] dist = new long[n + 1];
    for (int i = 1; i <= n; i++) {
      dist[i] = Long.MAX_VALUE;
    }
    
    ArrayList<Edge> arr = new ArrayList<>();
    for (int i = 0; i < m; i++) {
      String[] nums = br.readLine().split(" ");
      int a = Integer.parseInt(nums[0]);
      int b = Integer.parseInt(nums[1]);
      int c = Integer.parseInt(nums[2]);
      arr.add(new Edge(a, b, c));
    }
    
    dist[1] = 0;
    
    boolean isNagativeCycle = false;
    for (int i = 1; i <= n; i++) {
      isNagativeCycle = bellmanford(arr, dist, i, n);
    }
    
    if (isNagativeCycle) {
      System.out.println(-1);
    } else {
      for (int i = 2; i <= n; i++) {
        if (dist[i] == Long.MAX_VALUE) System.out.println(-1);
        else System.out.println(dist[i]);
      }
    }
  }

  private static boolean bellmanford(ArrayList<Edge> arr, long[] dist, int i, int n) {
    boolean ret = false;
    for (Edge e : arr) {
      if (dist[e.s] == Long.MAX_VALUE) continue;
      if (dist[e.e] > dist[e.s] + e.w) {
        dist[e.e] = dist[e.s] + e.w;
        if (i == n) {
          ret = true;
        }
      }
    }
    
    return ret;
  }
}

class Edge {
  int s, e, w;

  public Edge(int s, int e, int w) {
    super();
    this.s = s;
    this.e = e;
    this.w = w;
  }

}

위 문제에서 dist 배열의 자료형을 설정할 때 주의하자. int 로 지정하면 음수사이클에 의해서 언더플로우가 발생할 수 있다.

만약 그래프에서 음수사이클이 존재하는지만 판단하고 싶다면, 위 코드에서 dist 배열의 값이 무한대로 설정되어 있는지 체크하는 부분을 생략해도 된다. 또한 초기에 dist 배열에 어떤값으로 설정해도 된다.

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

package 최단경로.벨만포드.웜홀;

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

public class Main {
  public static void main(String[] args) throws NumberFormatException, IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int TC = Integer.parseInt(br.readLine());
    
    while(TC-- != 0) {
      String[] strs = br.readLine().split(" ");
      int n = Integer.parseInt(strs[0]);
      int m = Integer.parseInt(strs[1]);
      int w = Integer.parseInt(strs[2]);
      
      long[] dist = new long[n + 1];
      
      ArrayList<Edge> arr = new ArrayList<>();
      for (int i = 0; i < m; i++) {
        String[] nums = br.readLine().split(" ");
        int s = Integer.parseInt(nums[0]);
        int e = Integer.parseInt(nums[1]);
        int t = Integer.parseInt(nums[2]);
        
        arr.add(new Edge(s, e, t));
        arr.add(new Edge(e, s, t));
      }
      
      for (int i = 0; i < w; i++) {
        String[] nums = br.readLine().split(" ");
        int s = Integer.parseInt(nums[0]);
        int e = Integer.parseInt(nums[1]);
        int t = Integer.parseInt(nums[2]);
        
        arr.add(new Edge(s, e, -t));
      }
      
      boolean isNagativeCycle = false;
      for (int i = 1; i <= n; i++) {
        isNagativeCycle = bellmanfort(arr, dist, i, n);
      }
      
      if (isNagativeCycle) {
        System.out.println("YES");
      } else {
        System.out.println("NO");
      }
    }
  }

  private static boolean bellmanfort(ArrayList<Edge> arr, long[] dist, int i, int n) {
    boolean ret = false;
    for (Edge e : arr) {
      if (dist[e.e] > dist[e.s] + e.w) {
        dist[e.e] = dist[e.s] + e.w;
        if (i == n) {
          ret = true;
        }
      }
    }
    
    return ret;
  }
}

class Edge {
  int s, e, w;

  public Edge(int s, int e, int w) {
    super();
    this.s = s;
    this.e = e;
    this.w = w;
  }
}