벨만-포드 알고리즘이란?
그래프 자료구조에서 최단 거리를 구하는 알고리즘입니다. 그래프 상에서 정점간 최단 거리를 구하는 알고리즘에는 다익스트라 알고리즘이 많이 사용되고, 속도도 빠르지만 굳이 벨만 포드 알고리즘을 사용하는 이유는 음의 가중치가 나왔을 때 다익스트라가 사용불가능하기 때문입니다.
- 벨만 포드 알고리즘은 한 노드에서 다른 노드로 향하는 최단 거리를 구한다.
- 간선이 음의 가중치를 가져도 최단거리를 구할 수 있다.
- 시간 복잡도는
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. 음의 사이클 여부를 체크합니다.
- 무한 INF를 선언합니다.
- 거리를 표시하는 dist 배열을 INF로 초기화 합니다.
- 시작지점(start)를 0으로 초기화 해줍니다. 예를 들어 정점 1에서 정점 1로 향하는 거리는 항상 0입니다.
const INF = Number.MAX_SAFE_INTEGER;
const dist = Array(num+1).fill(INF);
dist[start] = 0;
최단 거리 테이블을 최신화 하는 로직을 (정점의 개수-1) 만큼 반복합니다.
정점의 최신화 되는 조건은 2가지 입니다.
- dist[정점]이 INF가 아니어야 합니다.
- (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-차이)
'Algorithm' 카테고리의 다른 글
코딩 테스트 알고리즘 공부 방법 순서 정리 (0) | 2022.10.11 |
---|---|
[Stack] 웹 브라우저 뒤로가기 앞으로가기 문제 (0) | 2022.10.11 |
플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm) Node.js (0) | 2022.08.04 |
[Algorithm] 조합 최적화 알고리즘 subsetSum Node.js (0) | 2022.08.02 |
[Algorithm] TSP 알고리즘(해밀턴 경로 방문 판매원 문제) Node.js (0) | 2022.07.31 |
댓글