9. 최단 경로 탐색: 벨만-포드 알고리즘(Bellman-Ford Algorithm)

벨만-포드 알고리즘은 다익스트라 알고리즘과 마찬가지로 최단 경로 탐색 알고리즘입니다. 노드와 가중치가 포함된 간선 정보를 이용하여 시작점과 도착점 사이의 최단 거리를 찾는 것이 이 알고리즘의 목적입니다. 설명만 들어서는 다익스트라 알고리즘과 일치합니다. 하지만 기본적인 최단 경로 탐색 알고리즘의 조건과 목적에 더하여 벨만-포드 알고리즘은 특정한 조건을 포함하고 있을 때 사용됩니다. 가중치에 음수가 포함된 경우입니다. 다익스트라 알고리즘은 기본적으로 가중치가 양수와 0으로 이루어져 있다는 것을 가정하고 있습니다. 그렇기 때문에 음수 가중치가 포함되어있다고 해도 알고리즘 자체에서 음수 가중치 부분을 처리할 수 없습니다. 

벨만-포드 알고리즘의 원리는 다음과 같습니다. 우리가 특정 노드에서 다른 어떤 노드로 이동하고자 할 때 경로에는 최대 전체노드수-1 만큼의 간선이 들어올 수 있을 것입니다. 즉 모든 노드들을 전부 방문하면서 이동하는 경우인 것입니다. 만일 최대 이동횟수인 전체노드수-1 횟수로 모든 간선을 체크하면서 노드 사이에 존재하는 경로의 가중치 값(혹은 비용)이 줄어들 수 있는지를 판단해보고 실제로 줄어들 수 있으면 줄어든 더 낮은 비용을 반영해주면서 문제를 풀이한다면 최종적으로는 노드 간 가중치 값을 최저로 낮출 수 있습니다. 이러한 논리 전개에 따라 문제를 풀때는 노드간 비용을 저장한 간선 정보리스트를 저장해두었다가 전체노드수-1회 루프를 돌면서 비용을 낮출 수 있는지 확인해줍니다. 우리의 가정에 따르면 전체노드수-1번 확인한 경로간 가중치값은 최저값이 되었을 것이므로, 여기서 1회 더 위의 로직을 작동시킨다고 하더라도 가중치 값에는 변동이 없어야할 것입니다. 만일 값이 변했다면 이는 노드간 가중치 값 중 음의 가중치를 갖고 있다는 뜻이 되며, 반복적으로 로직을 작동시키면 음의 가중치로 인한 사이클이 발생하여 음의 무한대로 가중치가 발산할 수 있다는 뜻이 됩니다. 그러므로 전체노드수-1회 루프를 태우면서 최소 가중치 값을 저장해주고, 마지막으로 1회 더 로직을 작동시킴으로써 음의 가중치로 인한 사이클 발생을 확인해볼 수 있습니다.

직접 문제를 풀면서 로직을 확인해보겠습니다.

11657번: 타임머신 - Baekjoon Online Judge

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

import java.io.BufferedReader;

import java.io.InputStreamReader;

import java.util.StringTokenizer;

class Edge {

  int from;

  int to;

  int cost;

  public Edge(int from, int to, int cost) {

    this.from = from;

    this.to = to;

    this.cost = cost;

  }

}

public class Main {

  private static final int MAX = (int) 1e9 + 1;

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

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    StringTokenizer st;

    st = new StringTokenizer(br.readLine().trim());

    int N = Integer.parseInt(st.nextToken());

    int M = Integer.parseInt(st.nextToken());

    int A, B, C;

    Edge[] edgeArray = new Edge[M];

    for (int i = 0; i < M; i++) {

      st = new StringTokenizer(br.readLine().trim());

      A = Integer.parseInt(st.nextToken());

      B = Integer.parseInt(st.nextToken());

      C = Integer.parseInt(st.nextToken());

      edgeArray[i] = new Edge(A, B, C);

    }

    int[] D = new int[N + 1];

    for (int i = 1; i <= N; i++) {

      D[i] = MAX;

    }

    D[1] = 0;

    for (int i = 0; i < N - 1; i++) {

      for (int j = 0; j < M; j++) {

        if (D[edgeArray[j].from] == MAX) {

          continue;

        }

        if (D[edgeArray[j].to] > D[edgeArray[j].from] + edgeArray[j].cost) {

          D[edgeArray[j].to] = D[edgeArray[j].from] + edgeArray[j].cost;

        }

      }

    }

    boolean flag = false;

    for (int j = 0; j < M; j++) {

      if (D[edgeArray[j].from] == MAX) {

        continue;

      }

      if (D[edgeArray[j].to] > D[edgeArray[j].from] + edgeArray[j].cost) {

        flag = true;

      }

    }

    if (flag) {

      System.out.println(-1);

    } else {

      for (int i = 2; i <= N; i++) {

        System.out.println(D[i] == MAX ? -1 : D[i]);

      }

    }

  }

}