[그래프] 벨만 포드 알고리즘

벨만-포드(Bellman-Ford) 알고리즘

 

1. 그래프에서 최단 경로를 찾는 알고리즘 중 하나

 

2. 간선비용이 양수,음수에서 모두 정상 동작함.

: 간선 비용은 시간,거리,요금을 나타내서 양수가 일반적임.

: 그러나 간선 비용이 음수인 경우에도 정상 동작함 (다익스크라는 음수인 간선에선 동작하지X)

 

3. 음수 사이클

: 음수 사이클이 있는 경우 거리를 무한히 줄이게되서, 최단 경로를 정의할 수 없음. (최단거리가 존재X)

---

구현 코드

출처 : 그림으로 이해하는 알고리즘

function bellmanFord(graph, start, end) {
  const numOfNodes = graph.length; // 10
  const distance = Array(numOfNodes).fill(Infinity); // [0, 8, 2, 4, 9, 10, 13]
  const predecessor = Array(numOfNodes).fill(null); // [null, 2, 0, 2, 1, 3, 5];
  distance[start] = 0;

  // V-1번 반복하며 최단 거리 갱신 (0~8)
  for (let i = 0; i < numOfNodes - 1; i++) {
    for (let [u, v, w] of graph) {
      if (distance[u] + w < distance[v]) {
        distance[v] = distance[u] + w;
        predecessor[v] = u;
      }
    }
  }

  // 음수 사이클 확인
  for (let [u, v, w] of graph) {
    if (distance[u] + w < distance[v]) {
      console.log('음수 사이클이 존재합니다.');
      return null;
    }
  }

  // 최단 경로 출력
  const path = []; // [0,2,3,5,6] [A,C,D,F,G]
  let currentNode = end;
  while (currentNode !== null) {
    path.unshift(currentNode);
    currentNode = predecessor[currentNode];
  }

  return { distance: distance[end], path: path };
}

// 그래프 예시: [출발노드, 도착노드, 가중치]
const graph = [
  // u  v  w
  [0, 1, 9], // A -> B 1 0
  [0, 2, 2], // A -> C 2 0
  [1, 4, 1], // B -> E 3 0
  [1, 3, 3], // B -> D 4 0
  [2, 3, 2], // C -> D 5 0
  [2, 5, 9], // C -> F 6 0
  [3, 4, 5], // D -> E 7 0
  [3, 5, 6], // D -> F 8 0
  [4, 6, 7], // E -> G 8 0
  [5, 6, 4], // F -> G
];

// 노드를 숫자로 매핑: A=0, B=1, C=2, D=3, E=4, F=5, G=6
const startNode = 0; // A
const endNode = 6; // G

const result = bellmanFord(graph, startNode, endNode);

if (result) {
  console.log('최단 거리:', result.distance);
  console.log(
    '최단 경로:',
    result.path.map((n) => String.fromCharCode(65 + n)).join(' -> ')
  );
}

 

---

벨만 포드 알고리즘

[백준]타임머신 - https://www.acmicpc.net/problem/11657

// SUCCESS
const file = require('fs').readFileSync('/dev/stdin').toString().split('\n');

const [n, m] = file[0].split(' ').map(Number); // n : 도시의 개수(노드), m : 버스 노선의 개수(간선)
const info = file.slice(1, m + 1).map(line => line.split(' ').map(Number));

const INF = 1e9;
const distance = new Array(n + 1).fill(INF);

function bellmanFord(start) {
    distance[start] = 0;
    
    for(let i = 0; i < n; i++) {
        for(let j = 0; j < m; j++) {
            const [currentNode, nextNode, cost] = info[j];
            if(distance[currentNode] !== INF && distance[nextNode] > distance[currentNode] + cost) {
                distance[nextNode] = distance[currentNode] + cost;
                
                if(i === n - 1) return true;
            }
        }
    }
    
    return false;
}

if(bellmanFord(1)) { // 음수 순환 확인되는 경우
    console.log(-1);
} else { // 1번 노드 다음부터 출력
    for(let i = 2; i <= n; i++) console.log(distance[i] === INF ? -1 : distance[i]);
}