최단 경로 3) 벨만 포드(Bellman-Ford) 알고리즘

벨만 포드 알고리즘

벨만 포드 알고리즘은 그래프 내에서 최단 경로를 찾는 알고리즘이다.

모든 간선의 비용이 양수일 때는 다익스트라 최단 경로 알고리즘을 사용하면 된다.

1번 노드에서 다른 노드로 가기 위한 최소 비용을 구해본다고 하자.

양수 간선

하지만 음수 간선이 포함된다면 어떻게 문제를 해결할 수 있을까?

음수 간선 포함

위의 그래프에는 음수 간선이 포함되어 있지만 여전히 최단 거리를 구할 수 있다.

하지만 음수 순환이 포함된다면 어떻게 문제를 해결할 수 있을까?

음수 순환 포함

위의 그래프에서는 음수 순환이 포함되어 있으며 이 경우 최단 거리가 음의 무한인 노드가 발생한다.

다익스트라 알고리즘을 사용한다면 저 음의 사이클을 계속해서 이동하게 되어 사용이 불가능하다.

이런 음수 간선이 포함된 상황에서 사용할 수 있는 알고리즘이 벨만 포드이다.

---

벨만 포드 알고리즘 동작 원리

1. 시작 노드 설정

2. 최단 거리 테이블 초기화

   • 시작 노드에 대해서 거리를 0으로 초기화
   • 나머지 노드는 거리를 무한으로 설정

3. 다음 과정을 정점 수(n) -1 만큼 반복

   • 매 반복 마다 모든 간선 확인
   • 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우, 거리 정보 갱신

• n-1번 반복 이후, n번째 반복에서도 거리 값이 갱신된다면 음수 순환이 존재

---

벨만 포드 알고리즘 VS 다익스트라 알고리즘

다익스트라 알고리즘

• 매번 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
• 음수 간선이 없다면 최적의 해를 찾을 수 있다.

벨만 포드 알고리즘

• 매번 모든 간선을 전부 확인한다.
• 따라서 다익스트라 알고리즘에서의 최적의 해를 항상 포함한다.
• 다익스트라 알고리즘에 비해서 시간이 오래 걸리지만 음수 순환을 탐지할 수 있다.

---

벨만 포드 알고리즘 소스코드

function bf(start) {
  // 시작 노드에 대해서 초기화
  dist[start] = 0;
  // 전체 n번의 라운드(round)를 반복
  for (let i = 0; i < n; i++) {
    // 매 반복마다 "모든 간선"을 확인하며
    for (let j = 0; j < m; j++) {
      let [cur, nextNode, cost] = edges[j];
      // 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
      if (dist[cur] != INF && dist[nextNode] > dist[cur] + cost) {
        dist[nextNode] = dist[cur] + cost;
        // n번째 라운드에서도 값이 갱신된다면 음수 순환이 존재
        if (i == n - 1) return true;
      }
    }
  }
  return false;
}

let INF = 1e9; // 무한을 의미하는 값으로 10억을 설정
let n = 6; // 노드의 개수
let m = 9; // 간선의 개수
// 모든 간선에 대한 정보를 담는 리스트 만들기
let edges = [
  // [a, b, c]: a에서 b로 가는 비용이 c라는 의미
  [1, 2, 6],
  [1, 3, 2],
  [2, 3, 2],
  [2, 4, 2],
  [3, 5, 1],
  [4, 6, 2],
  [5, 2, -4],
  [5, 4, 3],
  [5, 6, 4]
];
let dist = new Array(n + 1).fill(INF); // 최단 거리를 모두 무한으로 초기화
// 벨만 포드 알고리즘 수행
let negativeCycle = bf(1); // 1번 노드가 시작 노드
if (negativeCycle) console.log(-1);
else {
  for (let i = 2; i <= n; i++) {
    // 1번 노드를 제외한 다른 노드들로 가기 위한 최단 거리 출력
    // 도달할 수 없는 경우 -1을 출력
    if (dist[i] == INF) console.log(-1);
    // 도달할 수 있는 경우 거리를 출력
    else console.log(dist[i]);
  }
}

---

벨만 포드 문제 예제

예제) Baekjoon 11657 - 타임머신

💡 문제 확인

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다.

시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다.

1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.

💡 타임머신 문제의 해법

A지점에서 B로 이동할 때의 최단 거리를 구하는 문제이며 가중치가 양수가 아닌 경우도 고려해야하므로 벨만 포드 알고리즘을 사용할 수 있다.

💡 타임머신 문제 해결 코드

let INF = 1e9;

let node = 3;
let graph = [
  [1, 2, 4],
  [1, 2, 3]
];
let dist = Array(node + 1).fill(INF);

function df(start) {
  dist[start] = 0;
  for (let i = 0; i < node; i++) {
    for (let j = 0; j < graph.length; j++) {
      let [cur, next, cost] = graph[j];
      if (dist[cur] != INF && dist[next] > dist[cur] + cost) {
        dist[next] = dist[cur] + cost;
        if (i == node - 1) return true;
      }
    }
  }
  return false;
}

let cycle = df(1);
if (cycle) console.log(-1);
else {
  for (let i = 2; i <= node; i++) {
    if (dist[i] == INF) console.log(-1);
    else console.log(dist[i]);
  }
}

---

📑 참고 자료

패스트 캠퍼스: 프론트엔드 웹 개발의 모든 것 초격차 패키지