[c++] 다익스트라 알고리즘(Dijkstra's Algorithm) 최단 경로 알고리즘

08 Dec 2023

다익스트라 알고리즘 동작 방식

시작 정점을 선택하고 해당 정점까지의 최단 거리를 0으로 초기화합니다.
선택한 정점을 기준으로 인접한 정점들의 최단 거리를 갱신합니다.
방문하지 않은 정점 중 최단 거리를 갖는 정점을 선택하여 방문 처리합니다.
위 과정을 모든 정점을 방문할 때까지 반복합니다.

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

using namespace std;

#define V 6

vector<pair<int, int>> adj[V]; // 인접 리스트

vector<int> dijkstra(int src) {
    vector<int> dist(V, INT_MAX);  // 최단 거리를 저장할 배열
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;  // 우선순위 큐

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

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        for (auto i : adj[u]) {
            int v = i.first;
            int weight = i.second;
            if (dist[v] > dist[u] + weight) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }

    return dist;
}

int main() {
    adj[0].push_back({1, 5});
    adj[0].push_back({2, 1});
    adj[1].push_back({3, 3});
    adj[1].push_back({4, 7});
    adj[2].push_back({4, 5});
    adj[2].push_back({5, 2});
    adj[3].push_back({4, 1});
    adj[4].push_back({5, 3});

    vector<int> dist = dijkstra(0);
    for (int i = 0; i < V; i++) {
        cout << "Vertex " << i << ", Distance: " << dist[i] << endl;
    }
    return 0;
}

위 코드는 입력된 그래프에서 정점 0부터 다른 모든 정점까지의 최단 거리를 계산하는 다익스트라 알고리즘의 예시입니다.

Dijkstra 알고리즘을 이용하여 최단 경로를 구할 수 있으며, 이로써 네트워크 라우팅, GPS, 인공 지능, 휴리스틱 검색 등에서 많이 활용되고 있습니다. 하지만, 이 알고리즘은 음수 가중치가 있을 경우에는 사용할 수 없다는 한계가 있습니다.