[Algorithm] 벨만-포드 알고리즘 (Bellman-Ford) Node.js

벨만-포드 알고리즘이란?

그래프 자료구조에서 최단 거리를 구하는 알고리즘입니다. 그래프 상에서 정점간 최단 거리를 구하는 알고리즘에는 다익스트라 알고리즘이 많이 사용되고, 속도도 빠르지만 굳이 벨만 포드 알고리즘을 사용하는 이유는 음의 가중치가 나왔을 때 다익스트라가 사용불가능하기 때문입니다.

• 벨만 포드 알고리즘은 한 노드에서 다른 노드로 향하는 최단 거리를 구한다.
• 간선이 음의 가중치를 가져도 최단거리를 구할 수 있다.
• 시간 복잡도는 O(V\*E)다.

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

다익스트라 알고리즘은 현재 정점에서 연결된 가장 작은 가중치를 가진 정점을 선택하게 됩니다. 예를 들어 아래 그림에서 1번에서 3번으로 가는 최단거리를 구할 때 2가지 경로가 존재합니다.

• (1 >>> 3)으로 가면 거리는 10이 됩니다.
• (1 >>> 4 >>> 3)으로 가면 거리는 5가 됩니다.

문제는 다익스트라의 경우 음이 포함된 경우의 수를 선택할 수 없다는 점입니다. 따라서 다익스트라 알고리즘으로 최단거리는 항상 10이 출력됩니다. 방문하지 않은 정점 중에서 가중치가 가장 작은 정점을 찾는 과정을 단계별로 수행하기 때문입니다.

다익스트라의 장점은 빠른 시간복잡도 O(E * log V)를 가진다는 점입니다.

반면 벨만-포드 알고리즘의 경우 시작 정점에서 모든 경우의 수를 고려하게 되므로 (1 >>> 4 >>> 3) 이라는 경로를 선택하게 됩니다. 시간복잡도는 다소 느릴 수 있지만 음수를 포함한 가능한 모든 경우의 수를 고려하기 때문에 최적의 경로를 선택할 수 있게 됩니다. 음수를 포함해서 말이죠.,

벨만 포드 알고리즘 프로세스

1. 시작지점(src)를 지정합니다.

2. 최단거리 테이블을 초기화 합니다.

3. 정점의 갯수-1 만큼 위 과정을 반복합니다.

4. 음의 사이클 여부를 체크합니다.

1. 무한 INF를 선언합니다.
2. 거리를 표시하는 dist 배열을 INF로 초기화 합니다.
3. 시작지점(start)를 0으로 초기화 해줍니다. 예를 들어 정점 1에서 정점 1로 향하는 거리는 항상 0입니다.

const INF = Number.MAX_SAFE_INTEGER;
const dist = Array(num+1).fill(INF);
dist[start] = 0;

최단 거리 테이블을 최신화 하는 로직을 (정점의 개수-1) 만큼 반복합니다.

정점의 최신화 되는 조건은 2가지 입니다.

1. dist[정점]이 INF가 아니어야 합니다.
2. (dist[시작정점] + 가중치)가 dist[도착정점]보다 작아야 합니다.

for(let v=1; v<=num - 1; v++){
    edges.forEach((e)=>{
        const [src, dst, weight] = e;

        if(dist[src] !== INF && dist[src] + weight < dist[dst]){
            dist[dst] = dist[src] + weight;
        }
    })
}

벨만 포드 알고리즘에서는 음의 순환이 존재할 수 있습니다. 이를 체크해줍니다.

만약 distance 테이블이 업데이트 된다면 음의 순환이 존재하는 것입니다. 최단경로가 무한히 작아지는 현상입니다.

const hasNegative = edges.some((e)=>{
    const [src, dst, weight] = e;
    if(dist[src] !== INF && dist[src] + weight < dist[dst]){
        return true;
    }
});

마지막으로 음의 순환이 존재하는 경우 빈 배열을 반환합니다.

음의 순환이 없는 경우 0번째 요소를 제거한 배열을 반환합니다.

return hasNegative ? [] : dist.slice(1);

Reference

• 벨만 포드 알고리즘

  [플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm) Node.js

플로이드 알고리즘이란? 플로이드 워셜 알고리즘은 그래프 상에서 가능한 모든 경로의 최단거리를 뽑아내는 문제입니다. 플로이드 워셜 알고리즘의 시간복잡도는 O(V^3)입니다. 그래프 상에서

about-tech.tistory.com](https://about-tech.tistory.com/entry/플로이드-워셜-알고리즘-Floyd-Warshall-Algorithm-Nodejs)

[[Algorithm] 조합 최적화 알고리즘 subsetSum Node.js

조합 최적화 알고리즘은 주어진 배열 내에서 특정 조건을 만족하는 최적의 조합을 찾아내는 문제입니다. 조합(Combination)이란? 조합은 서로 다른 n개의 원소중에서 순서에 상관없이 r개의 원소를

about-tech.tistory.com](https://about-tech.tistory.com/entry/Algorithm-조합-최적화-알고리즘-subsetSum-Nodejs)

[[Algorithm] 백준 15649, 15650 JS 구현 ( 백트래킹 DFS 차이 )

백트래킹 알고리즘 백준 15649 N과 M 문제 링크 https://www.acmicpc.net/problem/15649 백트래킹을 이해하는 기본적인 알고리즘이다. 백트래킹 알고리즘이란 모든 경우의 수를 모두 고려하는 알고리즘이다.

about-tech.tistory.com](https://about-tech.tistory.com/entry/Algorithm-백준-15649-JS-구현-백트래킹-DFS-차이)