C++ 알고리즘) 최단 경로 알고리즘(다익스트라, 벨만-포드)

최단 경로 알고리즘

최단 경로 알고리즘은 그래프 내의 두 노드 사이를 이동할 때, 간선들의 가중치 총합이 최소가 되도록 하는 알고리즘이다.

1. 다익스트라 알고리즘

다익스트라는 현재 확정된 최단 거리 노드를 기준으로 주변 노드를 탐색하는 방식이다. 마치 물이 펴져 나가듯 가장 가까운 곳부터 채워나가는 느낌이다. (그리디 속성)

개념 및 작동 원리

1. 출발 노드를 설정하고 거리를 0으로 초기화한다.
2. 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택한다.
3. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최간 거리 테이블을 갱신한다.
4. 위 과정을 반복한다.

알고리즘 성능

1. 그래프의 표현
   1. 인접 행렬로 표현하면 O(v^2)
   2. 인접 리스트로 표현하면 O(v+e)
2. 알고리즘 동작
   1. 우선순위 큐(이진 힙)의 경우 O((v+e)log v)
   2. 우선순위 큐(피보나치 힙)의 경우 O(e+ vlogv)

인집 리스트를 활용해서 그래프를 구축하고 우선순위큐를 활용한다면 최종적으로 O((V + E) logV)이다.

한계

• 음의 가중치(Negative weight)가 있는 간선이 하나라도 있으면 사용할 수 없습니다. 이미 방문한 노드의 거리는 최단이라고 확정 짓기 때문입니다.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

#define INF 1e9 // 무한대 값 설정

// (비용, 목적지 노드) 쌍
typedef pair<int, int> pii;

void dijkstra(int start, vector<pii> adj[], int d[], int n) {
    // 최소 힙(Min-priority queue) 선언
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    
    d[start] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
        int dist = pq.top().first;
        int now = pq.top().second;
        pq.pop();

        // 현재 꺼낸 거리가 이미 기록된 거리보다 크다면 이미 방문한 것임
        if (d[now] < dist) continue;

        for (auto& edge : adj[now]) {
            int cost = dist + edge.first;
            // 다른 노드를 거쳐가는게 더 빠르다면 갱신
            if (cost < d[edge.second]) {
                d[edge.second] = cost;
                pq.push({cost, edge.second});
            }
        }
    }
}

---

2. 벨만-포드 알고리즘

모든 간선을 매번 확인하며 거리를 업데이트한다. "한 번의 라운드에서 최소 한 개의 노드는 최단 거리가 확정된다"는 원리를 이용해 총 V-1번 전체 간선을 훑는다. 다익스트라와 다른 점은 음의 가중치가 있는 경우에도 최단 경로를 찾을 수 있다.

이게 가능한 이유는 매 단계마다 모든 간선의 가중치를 다시 확인하여 최소 비용을 갱신하기 때문이다.

개념 및 작동 원리

1. 출발 노드를 0, 나머지는 무한대로 초기화한다.
2. 모든 간선을 하나씩 확인하며 최단 거리 테이블을 갱신한다.
3. 이 과정을 V-1번 반복한다.
4. 마지막으로 한 번 더 수행했을 때 값이 변한다면 음수 사이클이 존재한다는 뜻이다.

장점 및 한계

성능에서는 다익스트라보다 횔씬 느리다, 하지만 음의 가중치를 처리할 수 있기에 오직 음수 가중치나 사이클 감지가 필요할 때만 선택한다.

#include <iostream>
#include <vector>

using namespace std;

struct Edge {
    int from, to, cost;
};

#define INF 1e9

bool bellman_ford(int start, vector<Edge>& edges, long long d[], int n) {
    d[start] = 0;

    // n번 반복 (마지막 n번째는 음수 사이클 확인용)
    for (int i = 1; i <= n; i++) {
        for (auto& edge : edges) {
            int u = edge.from;
            int v = edge.to;
            int cost = edge.cost;

            if (d[u] != INF && d[v] > d[u] + cost) {
                d[v] = d[u] + cost;
                
                // n번째 라운드에서도 값이 갱신되면 음수 사이클 존재
                if (i == n) return true; 
            }
        }
    }
    return false;
}