Scribbly

플로이드 워셜 알고리즘에 아래와 같은 부분이 있었다.
graph[a][b] = Math.min(graph[a][b], graph[a][k] + graph[k][b]);
해당 부분을 '어떤 노드'가 업데이트 될 때 '다른 노드'에서 '또 다른 노드'로 가는 모든 경우의 수에 대해 실행하며 O(V^3)의 시간 복잡도로 최단거리 인접행렬을 출력하는 것을 볼 수 있었다.

모든 노드에서 다른 모든 노드로 가는 최단거리를 구하는 플로이드 워셜을 경로에 활용하여 '시작 노드'에서 '도착 노드'로 가는 최단거리를 구하는데 사용하면 어떨까? 새로운 노드에 방문할 때마다, 인접한 노드들에 대해 graph[a][b] = Math.min(graph[a][b], graph[a][k] + graph[k][b]);를 시행하는 것이다. 벨만-포드 알고리즘이다.

벨만-포드 알고리즘은 단순해보인다. 시간복잡도는 O(V*E)이다. 힙 자료구조를 사용하지 않는 다익스트라의 O(V^2)보다도 더 오래 걸리는 편이다.

그럼에도 벨만-포드는 다음의 경우에 유용하다.

간선 중 음의 가중치를 가지는 경우 - 다익스트라 알고리즘은 우선순위 큐와 while 문을 사용한다. 음의 가중치를 가진 간선을 넣으면, 해당 간선이 가장 먼저 튀어나온다. 음의 가중치가 매우 크다면, 음의 가중치를 무한하게 큐에 집어넣으면서 음의 무한으로 향하게 된다. 반면 플로이드 워셜과 벨만-포드 알고리즘은 최단경로 테이블을 가지고 있다. 같은 시행을 반복했을 때에 최단경로 테이블이 줄어든다면 음의 가중치를 가진 경로가 포함됨을 판별할 수 있다. 사실 대부분의 경우 한 경로를 한 번만 방문하므로 음의 가중치가 문제가 되지도 않는다.
(실생활에서) 테이블을 가지고 있는 것이 유리한 경우 - 인터넷으로 서울에서 캘리포니아까지 파일을 하나 보낸다고 가정해보자. 다익스트라를 위해 서울에서 캘리포니아까지 있는 모든 라우터의 갯수를 세어보자....그만 세어보자.
반면 서울-부산 100ms라는 테이블이 있고,
부산에서 부산-도쿄 300ms, 부산-하와이 400ms라는 테이블을 받고,
도쿄에서 도쿄-캘리포니아 500ms, 도쿄-하와이 1500ms,
하와이에서 하와이-캘리포니아 200ms, 하와이-도쿄 1500ms라는 테이블을 받았다고 해보자.
서울-부산-하와이-캘리포니아로 가는 경로가 700ms로 최단 경로임을 알 수 있다.
따라서 서울-캘리포니아 700ms라는 테이블 데이터가 하나 생긴다.
만일 하와이-캘리포니아 1000ms로 테이블이 업데이트 되었다고 해보자.
'서울-부산-하와이-캘리포니아'의 1500ms보다 '서울-부산-도쿄-캘리포니아'의 900ms가 더 적으므로 서울-캘리포니아 900ms로 테이블이 갱신된다.
이러한 방식을 '디스턴스 벡터 라우팅 프로토콜'이라고 하며, 벨만-포드 알고리즘이 사용되는 예시이다.
하와이에서 캘리포니아까지 가는 경로의 1000ms는 어떻게 구했냐고? 그건 서울에서 알 필요가 없다. 서울에서 캘리포니아까지의 900ms를 어떻게 구했는지도 알 필요 없는 것 처럼.

벨만-포드 알고리즘 구현

딥러닝 공부방 님이 정리한 코드를 참고했다.

const INF = 1e9;

// 노드 수, 간선 수 입력 받기
const n = 5;
const m = 5;
// 모든 간선에 대한 정보를 담는 리스트 생성
const edges = [
  [1, 2, -1],
  [1, 3, 4],
  [2, 3, 3],
  [2, 4, 2],
  [2, 5, 2],
];
// 최단 거리 테이블을 모두 무한으로 초기화
const dist = new Array(n + 1).fill(INF);

// 벨만 포드 알고리즘
function bellmanFord(start) {
  dist[start] = 0; // 시작 노드에 대해서 거리를 0으로 초기화
  for (let i = 0; i < n; i++) {
    // 정점 수만큼 반복
    for (let j = 0; j < m; j++) {
      // 매 반복 마다 모든 간선 확인
      const node = edges[j][0]; // 현재 노드 받아오기
      const next_node = edges[j][1]; // 다음 노드 받아오기
      const cost = edges[j][2]; // 가중치 받아오기
      // 현재 간선을 거려서 다른 노드로 이동하는 거리가 더 짧은 경우
      if (dist[node] !== INF && dist[next_node] > dist[node] + cost) {
        dist[next_node] = dist[node] + cost;
        // n번째 라운드에서도 값이 갱신된다면 음수 순환이 존재
        if (i === n - 1) {
          // n-1번 이후 반복에도 값이 갱신되면 음수 순환 존재
          return true;
        }
      }
    }
  }
  return false;
}

// 벨만 포드 알고리즘 수행
const negative_cycle = bellmanFord(1);

if (negative_cycle) {
  console.log("-1");
} else {
  console.log(dist); //[ 1000000000, 0, -1, 2, 1, 1 ]
}

scribbly.

scribbly.

scribbly.

벨만-포드 알고리즘 구현