최단 경로 문제들을 풀며, 다양한 알고리즘이 있다는 걸 알았다.
다 비슷한 모양의 코드같지만, 개념들을 확고히 다지고 알고 넘어가면 놓을 것 같아 정리해본다.
다익스트라, 벨만-포드, 플로이드-워셜 알고리즘은 그래프에서 최단 경로를 구하는 알고리즘이다.
세 가지 모두 그래프 문제를 해결할 때 유용하지만, 각각의 특성과 사용 조건이 다르다.
1. 다익스트라 알고리즘 (Dijkstra’s Algorithm)
개념:
다익스트라 알고리즘은 하나의 시작점에서 모든 다른 노드까지의 최단 경로를 구하는 알고리즘이다. 가중치가 음수가 없는 그래프에서만 동작하며, 최단 경로를 탐색할 때 우선순위 큐(최소 힙)를 사용해 가장 짧은 경로를 점차적으로 확장한다.
어떻게 동작하나?
- 시작 노드에서 출발해, 그 노드까지의 거리를 0으로 초기화한다. 나머지 노드는 무한대로 설정한다.
- 우선순위 큐에서 가장 작은 가중치를 가진 노드를 꺼내고, 이 노드와 연결된 이웃 노드들의 거리를 업데이트한다.
- 업데이트된 이웃 노드를 다시 큐에 넣고, 반복적으로 가장 짧은 경로를 찾는다.
- 큐가 비게 될 때까지 이 과정을 반복하면 모든 노드까지의 최단 경로를 알 수 있다.
예시:
예를 들어, 도시 A에서 B, C, D로 가는 그래프가 있다고 하자. 간선의 가중치는 각각 다음과 같다:
- A → B (4), A → C (2), C → B (1), B → D (5), C → D (8)
이 그래프에서 다익스트라 알고리즘을 실행하면, A에서 D까지의 최단 경로는 A → C → B → D이고, 그 총 비용은 7이다.
언제 사용하나?
다익스트라는 주로 가중치가 양수인 경우에 최단 경로를 찾을 때 사용한다. 특히, 빠른 속도가 요구되는 대규모 네트워크에서 매우 유용하다.
장점과 단점:
- 장점: 음수가 없는 그래프에서 매우 빠르다.
- 단점: 음수 가중치가 포함된 그래프에서는 올바른 결과를 보장하지 못한다.
코드 구현
class MinHeap {
constructor() {
this.heap = [];
}
push([node, dist]) {
this.heap.push([node, dist]);
this.bubbleUp();
}
bubbleUp() {
let idx = this.heap.length - 1;
const last = this.heap[idx];
while (idx > 0) {
let parentIdx = Math.floor((idx - 1) / 2);
if (this.heap[parentIdx][1] <= last[1]) break;
this.heap[idx] = this.heap[parentIdx];
idx = parentIdx;
}
this.heap[idx] = last;
}
pop() {
const top = this.heap[0];
const last = this.heap.pop();
if (this.heap.length > 0) {
this.heap[0] = last;
this.bubbleDown();
}
return top;
}
bubbleDown() {
let idx = 0;
const length = this.heap.length;
const node = this.heap[0];
while (true) {
let leftChildIdx = 2 * idx + 1;
let rightChildIdx = 2 * idx + 2;
let swapIdx = null;
if (leftChildIdx < length && this.heap[leftChildIdx][1] < node[1]) {
swapIdx = leftChildIdx;
}
if (rightChildIdx < length && this.heap[rightChildIdx][1] < (swapIdx === null ? node[1] : this.heap[swapIdx][1])) {
swapIdx = rightChildIdx;
}
if (swapIdx === null) break;
this.heap[idx] = this.heap[swapIdx];
idx = swapIdx;
}
this.heap[idx] = node;
}
isEmpty() {
return this.heap.length === 0;
}
}
function dijkstra(start, graph, n) {
const distances = Array(n).fill(Infinity);
distances[start] = 0;
const minHeap = new MinHeap();
minHeap.push([start, 0]);
while (!minHeap.isEmpty()) {
const [currentNode, currentDist] = minHeap.pop();
if (distances[currentNode] < currentDist) continue;
for (const [nextNode, weight] of graph[currentNode]) {
const newDist = currentDist + weight;
if (newDist < distances[nextNode]) {
distances[nextNode] = newDist;
minHeap.push([nextNode, newDist]);
}
}
}
return distances;
}
조건:
- 그래프에 음수 간선이 없을 때.
- 단일 시작점에서 모든 노드까지 최단 경로를 구할 때
2. 벨만-포드 알고리즘 (Bellman-Ford Algorithm)
개념:
벨만-포드 알고리즘은 하나의 시작점에서 모든 노드까지의 최단 경로를 구하는 알고리즘으로, 음의 가중치가 있는 그래프에서도 동작한다. 이 알고리즘은 다익스트라와 달리 모든 간선을 반복적으로 확인해 최단 경로를 찾는다.
어떻게 동작하나?
- 모든 노드의 거리를 무한대로 초기화하고, 시작 노드의 거리는 0으로 설정한다.
- 모든 간선을 반복적으로 확인하며, 노드 간 거리를 업데이트한다. 각 노드에서 모든 간선을 최대 V-1번 반복 확인한다.
- 모든 간선을 다 돌고 나서도 경로가 업데이트된다면, 이는 음의 사이클이 존재함을 의미한다.
예시:
- 노드 A → B (4), A → C (3), C → B (-2), B → D (5)
이 그래프에서 벨만-포드를 실행하면, A에서 D까지의 최단 경로는 A → C → B → D이고, 그 총 비용은 6이다. C → B의 음의 가중치를 고려해 최적 경로를 찾을 수 있다.
언제 사용하나?
벨만-포드는 음의 가중치가 있는 그래프에서 사용한다. 특히, 음의 사이클이 존재하는지 확인해야 할 때 매우 유용하다.
장점과 단점:
- 장점: 음의 가중치가 있는 그래프에서도 최단 경로를 찾을 수 있다.
- 단점: 모든 간선을 V-1번씩 확인하므로, 시간 복잡도가 **O(V * E)**로 느리다.
function bellmanFord(start, edges, n) {
const distances = Array(n).fill(Infinity);
distances[start] = 0;
// V-1번 반복
for (let i = 0; i < n - 1; i++) {
for (const [u, v, weight] of edges) {
if (distances[u] !== Infinity && distances[u] + weight < distances[v]) {
distances[v] = distances[u] + weight;
}
}
}
// 음수 사이클 탐지
for (const [u, v, weight] of edges) {
if (distances[u] !== Infinity && distances[u] + weight < distances[v]) {
return 'Negative cycle detected';
}
}
return distances;
}조건:
- 음의 가중치가 있는 간선이 포함된 그래프에서 최단 경로를 구할 수 있다.
- 음의 사이클이 있는지 확인할 때 유용하다.
3. 플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm)
개념:
플로이드-워셜 알고리즘은 모든 노드 쌍 간의 최단 경로를 구하는 알고리즘이다. 벨만-포드나 다익스트라와는 다르게, 모든 노드에서 모든 노드까지의 경로를 한꺼번에 계산할 수 있다. 이 알고리즘은 동적 계획법을 기반으로 동작하며, 그래프 내의 모든 경로를 고려해 최단 경로를 찾는다.
어떻게 동작하나?
- 모든 노드 쌍의 거리를 행렬로 나타낸다. 만약 직접 연결된 간선이 없다면 무한대로 표시한다.
- 각 노드를 중간 노드로 설정하고, 이 중간 노드를 거쳐가는 경로가 더 짧은지 확인해 행렬을 업데이트한다.
- 이 과정을 노드의 수만큼 반복해, 모든 노드 쌍 간의 최단 경로를 계산한다.
예시:
노드 A, B, C가 있는 그래프에서, 각 경로가 다음과 같다고 하자:
- A → B (5), A → C (9), B → C (2)
플로이드-워셜을 실행하면 A → C의 최단 경로는 A → B → C로, 그 비용은 7이 된다.
언제 사용하나?
플로이드-워셜은 모든 노드 쌍 간의 경로를 한꺼번에 계산해야 하는 경우에 사용한다. 노드 수가 적은 경우에는 매우 효과적이다. 예를 들어, 교통 네트워크 분석이나 모든 사람 간의 최단 경로를 계산해야 하는 사회적 연결망 분석에 유용하다.
장점과 단점:
- 장점: 모든 노드 간 최단 경로를 동시에 계산할 수 있다.
- 단점: 시간 복잡도가 **O(V³)**로, 노드 수가 많으면 비효율적이다.
function floydWarshall(graph, n) {
const dist = Array.from({ length: n }, () => Array(n).fill(Infinity));
for (let i = 0; i < n; i++) {
dist[i][i] = 0;
}
for (let [u, v, weight] of graph) {
dist[u][v] = weight;
}
for (let k = 0; k < n; k++) {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
return dist;
}
조건:
- 모든 노드 쌍 간의 최단 경로를 구할 때 유용하다.
- 노드 수가 적은 경우에 효율적이며, 시간 복잡도는 O(V³).
- 음의 가중치가 포함된 그래프에서도 동작하지만, 음의 사이클은 탐지하지 않는다.
3. 플로이드 워셜 vs 다익스트라: 언제 어떤 알고리즘을 사용할까?
플로이드 워셜을 사용하는 경우:
- 모든 정점 쌍 사이의 최단 경로를 구해야 한다.
- 문제에서 "모든 정점 쌍 간의 최단 경로"가 필요하다고 명시되어 있는 경우.
- 예시: 여행 경로 최적화, 모든 도시 쌍 간의 최단 경로, 모든 사람 간의 연결성 계산.
- 정점의 수가 작다(대략 100 이하).
- 정점 수가 많으면 O(N3)O(N^3)의 시간 복잡도가 성능에 큰 영향을 미치기 때문에 적합하지 않습니다.
- 간접 경로를 반드시 고려해야 할 때.
- 경유지나 중간 지점을 통해서 가는 경로를 탐색하는 경우.
다익스트라를 사용하는 경우:
- 단일 출발점에서 모든 다른 정점까지의 최단 경로가 필요하다.
- 예시: 한 출발지에서 목적지까지의 최단 경로 찾기.
- 그래프가 크고(정점이나 간선이 많을 때), 양의 가중치만 있을 때.
- 음의 가중치가 없고, 그래프가 큰 경우, 다익스트라의 시간 복잡도 O((N+E)logN)O((N + E) \log N)가 성능 면에서 우수하다.
- 출발점이 고정된 상황에서 최단 경로를 구해야 할 때.
- 예를 들어, 도시 내의 특정 위치에서 모든 다른 위치로 가는 경로를 계산해야 할 때.
정리
- 다익스트라: 음의 가중치가 없는 그래프에서 단일 시작점의 최단 경로를 구할 때 사용한다. 시간 복잡도가 효율적이며, 네트워크 문제나 경로 탐색에 적합하다.
- 벨만-포드: 음의 가중치가 있는 그래프에서도 최단 경로를 구할 수 있다. 특히 음의 사이클을 탐지하는 문제에서 유용하다.
- 플로이드-워셜: 모든 노드 쌍 간의 최단 경로를 구하는 문제에 적합하다. 노드 수가 적은 경우에는 효과적이지만, 대규모 그래프에서는 비효율적일 수 있다.
'알고리즘' 카테고리의 다른 글
| Segment Tree - 구간 트리 2 (0) | 2025.05.22 |
|---|---|
| Segment Tree - 구간트리 (0) | 2025.05.13 |
| nodejs - 연결리스트 (0) | 2024.06.20 |
| 시간복잡도 이해하기 (0) | 2024.06.15 |
| Nodejs - 이진탐색 (0) | 2024.04.22 |