DJIKSTRA

다익스트라 알고리즘은 가중치가 있는 그래프에서 하나의 시작점으로부터 모든 정점까지의 최단 거리를 구하는 알고리즘이다.

특징

음수 가중치가 없는 그래프에서만 사용 가능
시간복잡도: O(E log V) (우선순위 큐 사용 시)
그리디 알고리즘의 일종

사용 예시

네비게이션 최단 경로
네트워크 라우팅
게임에서 캐릭터 이동 경로

동작 원리

핵심 아이디어

시작 정점의 거리를 0으로, 나머지는 무한대(INF)로 초기화
아직 방문하지 않은 정점 중 거리가 가장 짧은 정점을 선택
해당 정점을 거쳐 다른 정점으로 가는 거리가 더 짧으면 갱신 (relaxation)
모든 정점을 방문할 때까지 2-3 반복

구현

3.1 기본 구현 (인접 리스트 + 우선순위 큐)

c++

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

const int INF = 1e9;

vector<int> dijkstra(int start, vector<vector<pair<int, int>>>& graph) {
    int n = graph.size();
    vector<int> dist(n, INF);
    
    // 최소 힙: {거리, 정점}
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    
    dist[start] = 0;
    pq.push({0, start});
    
    while (!pq.empty()) {
        auto [curDist, cur] = pq.top();
        pq.pop();
        
        // 이미 처리된 정점이면 스킵
        if (curDist > dist[cur]) continue;
        
        // 인접 정점 탐색
        for (auto& [next, weight] : graph[cur]) {
            int newDist = curDist + weight;
            
            // 더 짧은 경로 발견 시 갱신
            if (newDist < dist[next]) {
                dist[next] = newDist;
                pq.push({newDist, next});
            }
        }
    }
    
    return dist;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int V, E, start;
    cin >> V >> E >> start;
    
    // 인접 리스트: graph[u] = {{v1, w1}, {v2, w2}, ...}
    vector<vector<pair<int, int>>> graph(V + 1);
    
    for (int i = 0; i < E; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
        // 무방향 그래프면: graph[v].push_back({u, w});
    }
    
    vector<int> dist = dijkstra(start, graph);
    
    // 결과 출력
    for (int i = 1; i <= V; i++) {
        if (dist[i] == INF) cout << "INF\n";
        else cout << dist[i] << '\n';
    }
    
    return 0;
}

3.2 경로 추적 (최단 경로 역추적)

최단 거리뿐만 아니라 실제 경로도 알고 싶을 때 사용한다.

c++

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

const int INF = 1e9;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int V, E, start, end;
    cin >> V >> E >> start >> end;
    
    vector<vector<pair<int, int>>> graph(V + 1);
    for (int i = 0; i < E; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
    }
    
    vector<int> dist(V + 1, INF);
    vector<int> parent(V + 1, -1);  // 경로 추적용
    
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    
    dist[start] = 0;
    pq.push({0, start});
    
    while (!pq.empty()) {
        auto [curDist, cur] = pq.top();
        pq.pop();
        
        if (curDist > dist[cur]) continue;
        
        for (auto& [next, weight] : graph[cur]) {
            int newDist = curDist + weight;
            
            if (newDist < dist[next]) {
                dist[next] = newDist;
                parent[next] = cur;  // 이전 정점 기록
                pq.push({newDist, next});
            }
        }
    }
    
    // 최단 거리 출력
    cout << dist[end] << '\n';
    
    // 경로 역추적
    vector<int> path;
    int cur = end;
    while (cur != -1) {
        path.push_back(cur);
        cur = parent[cur];
    }
    
    // 역순으로 출력 (start -> end)
    cout << path.size() << '\n';
    for (int i = path.size() - 1; i >= 0; i--) {
        cout << path[i] << ' ';
    }
    
    return 0;
}