[알고리즘]- 다익스트라 C++기본 코드 구조

1. 다익스트라란 ?

 

음수 사이클이 없는 그래프에서 한 정점에서 모든 정점까지의 최단거리를 구하는 방법입니다.

각 단계에서 가장 짧은 경로를 선택하며 진행하기 때문에 그리디의 성질을 가지고 있습니다. 힙으로 그리디 성질을 이용합니다.

 

 

각 노드 사이에 가중치가 있고 방향이 있든 없든 상관이 없습니다.

https://ko.wikipedia.org/wiki/%EB%8D%B0%EC%9D%B4%ED%81%AC%EC%8A%A4%ED%8A%B8%EB%9D%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

 

기본 코드 구조는 다음과 같습니다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <functional> // for std::greater
#include <climits>    // for INT_MAX

using namespace std;

const int INF = INT_MAX; // 무한대를 나타내는 상수 (최댓값)

vector<vector<pair<int, int>>> graph; // 인접 리스트 (정점, 가중치)

// 다익스트라 알고리즘 함수
void dijkstra(int start, int N) {
    // 최단 거리 저장용 배열 (초기에는 모두 무한대)
    vector<int> dist(N + 1, INF);
    dist[start] = 0; // 시작점의 거리는 0으로 설정

    // 우선순위 큐 (최소 힙, 거리 기준 오름차순 정렬)
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start}); // (거리, 정점) 삽입

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

        // 이미 더 짧은 경로가 있다면 스킵
        if (dist[cur] < cur_dist) continue;

        // 인접한 모든 정점에 대해 거리 갱신
        for (auto& edge : graph[cur]) {
            int next = edge.first;
            int weight = edge.second;

            int next_dist = cur_dist + weight;
            // 더 짧은 경로를 찾았다면 갱신하고 우선순위 큐에 삽입
            if (dist[next] > next_dist) {
                dist[next] = next_dist;
                pq.push({next_dist, next});
            }
        }
    }

    // 결과 출력
    for (int i = 1; i <= N; ++i) {
        if (dist[i] == INF)
            cout << "INF "; // 경로가 없는 경우
        else
            cout << dist[i] << " "; // 최단 거리 출력
    }
    cout << endl;
}

int main() {
    int N, M; // N: 정점 수, M: 간선 수
    cin >> N >> M;

    graph.resize(N + 1); // 그래프 크기 조정 (1-indexed)

    // 간선 입력
    for (int i = 0; i < M; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w}); // u -> v의 가중치 w
        graph[v].push_back({u, w}); // 무방향 그래프일 경우
    }

    int start;
    cin >> start; // 시작 정점 입력

    // 다익스트라 알고리즘 실행
    dijkstra(start, N);

    return 0;
}

 

이 코드를 꼼꼼히 이해하고 반복적 학습을 통해 외울 정도로 훈련해야합니다.