[c++] 다익스트라 알고리즘

08 Dec 2023

다익스트라 알고리즘은 그래프에서 한 지점에서 다른 모든 지점까지의 최단 경로를 찾는 알고리즘입니다. 각 지점 사이의 거리 또는 가중치가 있는 그래프에서 사용됩니다.

알고리즘 동작 방식

출발 지점을 기준으로 인접한 모든 노드까지의 거리를 기록합니다.
기록한 거리와 비교하여 현재까지의 최단 거리보다 더 짧은 거리를 발견하면 최단 거리를 업데이트합니다.
방문하지 않은 노드 중에서 가장 거리가 짧은 노드를 선택하여 해당 노드를 기준으로 위 과정을 반복합니다.

예제 코드

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

#define INF INT_MAX

vector<vector<pair<int, int>>> graph; // 그래프 정보
vector<int> distance; // 출발 지점으로부터의 최단 거리

void dijkstra(int start) {
    priority_queue<pair<int, int>> pq;
    pq.push({0, start});
    distance[start] = 0;

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

        if (distance[cur] < dist) continue;

        for (auto& next : graph[cur]) {
            int nextDist = dist + next.second;
            if (nextDist < distance[next.first]) {
                distance[next.first] = nextDist;
                pq.push({-nextDist, next.first});
            }
        }
    }
}

사용 예

int main() {
    int n, m; // 노드의 개수, 간선의 개수
    cin >> n >> m;
    
    graph.resize(n + 1);
    distance.resize(n + 1, INF);

    for (int i = 0; i < m; ++i) {
        int from, to, cost;
        cin >> from >> to >> cost;
        graph[from].push_back({to, cost});
    }

    int start; // 출발 지점
    cin >> start;

    dijkstra(start);

    for (int i = 1; i <= n; ++i) {
        if (distance[i] == INF) {
            cout << "INFINITY" << "\n";
        } else {
            cout << distance[i] << "\n";
        }
    }

    return 0;
}

위 코드는 다익스트라 알고리즘을 사용하여 출발 지점으로부터 각 지점까지의 최단 거리를 구하는 예제입니다.

요약

다익스트라 알고리즘은 최단 경로 문제를 푸는 데 사용되는 알고리즘으로, 효율적인 구현과 함께 그래프에서 최단 거리를 찾는 데 활용됩니다.

참고 자료

위키백과: 다익스트라 알고리즘