[알고리즘 / Java] 벨만 포드 알고리즘

안녕하세요!
최단 경로 알고리즘으로 다익스트라 알고리즘과 플로이드 워셜알고리즘이 많이 알려져 있습니다.
오늘은 또다른 최단 경로 알고리즘인 벨만 포드 알고리즘을 소개시켜 드리고자 이번 포스팅을 하게되었습니다.

벨만 포드 알고리즘을 소개하기 이전에,
다익스트라 알고리즘 및 플로이드 워셜 알고리즘의 한계점을 먼저 알고가면, 벨만 포드 알고리즘을 이해하는데 큰 도움이 되기 때문에
이 부분부터 먼저 살펴보도록 하겠습니다!

 

 

---

 

다익스트라 알고리즘의 한계

이번 포스팅에서는 다익스트라 및 플로이드 워셜 알고리즘에 대한 설명을 따로 하지 않고,
다음에 기회가 되면 이 두가지 알고리즘에 대해 따로 포스팅하도록 하겠습니다.

다익스트라 알고리즘은 그리디(Greedy) 알고리즘을 기반으로 구현합니다.
시작점을 기준으로 연결된 노드의 최소 거리를 선택해 더해나가는데, 이 논리에는 모순이 존재합니다..!
바로 음수의 가중치를 갖게되면 알고리즘에 모순이 생기게 되는 것인데요.
간단한 예를 살펴보도록 하겠습니다.

위의 그래프에서 A를 시작점으로 C에 대한 최단 경로를 다익스트라 알고리즘을 통해 구해보면 A →C (4) 가 됩니다.
사실은 A→B→C (-90) 가 정답인데, 왜 이런 결과가 나오게 될까요?
A에서 출발해서 다음 노드로 B와 C를 갈 수 있습니다. 여기서 C의 노드에 대한 최단거리는 4로 갱신되게 됩니다.
이에 따라 A→B (10) 로 이동한 이후 C를 방문하려할 때, 이미 방문한 노드이므로 최단거리를 갱신하지 않습니다.

 

플로이드 워셜 알고리즘의 한계

플로이드 워셜 알고리즘에서는 임의의 3개의 노드 a, b, k에 대하여 dp[a][b] = dp[a][k] + dp[k][b] 의 점화식을 이용하여 최단 경로를 구합니다.
구현이 간단하다는 장점이 있지만, O(n^3) 이라는 큰 시간복잡도를 가진다는 한계가 있습니다.

 

 

---

 

벨만 포드 알고리즘

벨만 포드 알고리즘의 가장 큰 특징은 음의 가중치 를 가질 수 있다는 점입니다.
그래서 음의 가중치를 가져 다익스트라 알고리즘으로 해결하지 못하는 문제를 해결할 수 있습니다.

정점의 개수를 N, 간선의 개수를 M이라고할 때, 벨만 포드 알고리즘은 O(N*M) 의 시간 복잡도를 가집니다.
다익스트라 알고리즘은 시작점을 기준으로 연결된 노드들을 최소거리를 항상 보장하는 경우에만 탐색을 했다면, 벨만 포드 알고리즘은 시작점의 최소거리를 0으로 초기화하고, 모든 정점들에 해당하는 간선들을 모두 탐색합니다.
(단, 간선의 가중치와 시작점에서 정점까지의 거리의 합이 해당 간선이 도달하고자 하는 정점의 기존 거리보다 작을 때 갱신합니다.)
또한, 벨만 포드 알고리즘을 구현한 이후 모든 정점에 대해 간선을 다시 확인해서 만약 기존 거리보다 더 작은 값이 발생할 때 음수 사이클이 존재한다고 할 수 있습니다.

소스 코드

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

class Main {

  static final long INF = Long.MAX_VALUE;
  int n;
  int m;
  ArrayList<ArrayList<Node>> graph = new ArrayList<>();
  long[] dp = new long[n];

  public static void main(String[] args) throws Exception {
    ...
    dp = new long[n + 1];
    ...
    // 모든 원소를 INF로 초기화
    Arrays.fill(dp, INF);

    // 벨만 포드 알고리즘 수행 (시작점 : 1)
    bellmanFord(1);

    if (findNegativeCycle()) {
        // 음수 사이클이 발생
    } else {
        // 음수 사이클이 발생하지 않음
    }
    ...
  }

  public void bellmanFord(int start) {
    dp[start] = 0;

    for (int i = 0; i < n; i++) {    // 모든 정점에 대하여
      for (int now = 1; now <= n; now++) {    // 모든 간선에 대하여
        for (Node node : graph.get(now)) {
          int next = node.getIndex();
          long cost = dp[now] + node.getDistance();

          if (dp[now] != INF && dp[next] > cost) dp[next] = cost;
        }
      }
    }
  }

  public boolean findNegativeCycle() {
    for (int now = 1; now <= n; now++) {
      for (Node node : graph.get(now)) {
        int next = node.getIndex();
        long cost = dp[now] + node.getDistance();

        if (dp[now] != INF && dp[next] > cost) return true;
      }
    }

    return false;
  }
}

class Node {

  private int index;
  private long distance;    // 가중치

  public Node(int index, long distance) {
    this.index = index;
    this.distance = distance;
  }

  public int getIndex() {
    return this.index;
  }

  public long getDistance() {
    return this.distance;
  }
}