[Algorithm] 벨만포드 알고리즘

오늘은 딕스트라 알고리즘에 이은 벨만 포드!

 

음수의 값이 있을 때 최단거리를 구하는 데 사용할 수 있다. 

 

실제 상황에서 음수 거리라는 게 있을 수는 없지만... 저번 코딩 테스트 문제로 나와 당황했던 기억이 있으니 오늘 한번 풀어보려고 한다. 

 

방식은 아래와 같다. 

 

1. 노드 수만큼 최단거리를 표시하는 배열을 생성한다. 이 때 시작점을 제외하고는 INF 값을 넣는다. 시작점은 0을 넣어준다.

2. 노드 수 만큼 루프 하면서 모든 간선을 루핑 하는데 이때 최단거리에서 INF가 아닌 시작점이면서 도착점까지의 거리에 가중치를 더했을 때 현재의 거리보다 작아진다면 최단거리 배열을 수정한다. 

3. 마지막으로 위 과정을 한번 더 적용했을 때 만약 최단거리가 또 수정된다면 이는 무한 루프에 빠진 것으로 정답이 없는 게 답.

 

자바스크립트 코드 구현

function BellmanFord(num, edges, start) {
  let INF = Infinity;
  let dist = Array(num + 1).fill(INF);
  dist[start] = 0;

  for (let i = 0; i < num; i++) {
    edges.forEach((element, index) => {
      let [start, destination, value] = element;
      if (dist[start] !== INF && dist[start] + value < dist[destination]) {
        dist[destination] = dist[start] + value;
      }
    })
  }

  const isInfiniteLoop = edges.some((element, index) => {
    let [start, destination, value] = element;
    if (dist[start] !== INF && dist[start] + value < dist[destination]) {
      return true;
    }
  })
  
  return isInfiniteLoop ? [] : dist.slice(1, dist.length);
}