[알고리즘] C++로 이해하는 다익스트라(Dijkstra)

---

☑️ C++로 이해하는 다익스트라(Dijkstra)

다익스트라 알고리즘은 최단 경로를 구하는 알고리즘이다. 한 정점에서 모든 정점까지의 최단 경로를 구하면서 각 정점까지의 최단 경로를 모두 찾는다. 오래된 알고리즘이라서 이를 개선하거나 영향을 받은 알고리즘도 많은데, 각각 A* 알고리즘, 벨만-포드 알고리즘, 플로이드-워셜 알고리즘 등이 있다.

 

☑️ 다익스트라 알고리즘 프로세스

1. 각 노드의 거리를 무한대로 초기화한다.
2. 시작노드의 거리는 0으로 설정한다.
3. 이전 노드를 저장할 공간을 Null로 설정한다.
4. 방문하지 않은 노드 집합 Q에 모든 노드를 추가한다.
5. 노드 집합 Q가 비어있지 않다면 반복한다
   1. Q에서 Dist가 가장 작은 노드를 선택한다.
   2. Q에서 선택한 노드를 제거한다.
   3. 선택 노드의 인접 노드를 순회한다.
      1. 새로운 거리를 확인하고 인접 노드 거리보다 작으면 갱신한다

 

☑️ 다익스트라 알고리즘의 장단점

 ▶️ 장점

• 최단 거리를 보장한다.
• 우선순위 큐와 함께 사용할 시에 효율적으로 작동한다.

 

▶️ 단점

• 음수 가중치가 있는 그래프에서는 사용이 불가능하다.
• 모든 정점에 대해서 계산하게 된다.
• 밀집된 그래프에서는 느려질 수 있다.

 

☑️ 시간 복잡도

다익스트라 알고리즘은 그래프 표현 방식과 구현 방식에 따라서 달라질 수 있다.

• 우선순위 큐 사용 : O(V+E log)
• 선형 검색 : O(V^2)

 

☑️ 다익스트라 알고리즘 구현(C++)

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

using namespace std;

using pii = pair<int, int>;

const int INF = numeric_limits<int>::max();

vector<int> dijkstra(int start, const vector<vector<pii>>& graph) {
    int n = graph.size();
    vector<int> dist(n, INF);
    priority_queue<pii, vector<pii>, greater<>> pq;

    dist[start] = 0;
    pq.push({0, start});

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

        if (cost > dist[now]) continue;

        for (const auto& [next_cost, next] : graph[now]) {
            int total_cost = cost + next_cost;
            if (total_cost < dist[next]) {
                dist[next] = total_cost;
                pq.push({total_cost, next});
            }
        }
    }

    return dist;
}

int main() {
    vector<vector<pii>> graph(4);
    graph[0].push_back({2, 1});
    graph[0].push_back({1, 2});
    graph[1].push_back({3, 3});
    graph[2].push_back({1, 3});

    int start = 0;
    vector<int> distances = dijkstra(start, graph);

    for (int i = 0; i < distances.size(); ++i) {
        if (distances[i] == INF)
            cout << "노드 " << i << ": 도달 불가" << endl;
        else
            cout << "노드 " << i << ": " << distances[i] << endl;
    }

    return 0;
}