[알고리즘] Dijkstra, 다익스트라 알고리즘

문제 정의

• 문제유형
  • 한개의 노드에서 다른 노드까지의 최소 비용 구할때
    • 한 노드에서 다른 노드까지 최소비용을 구하는 문제라면 다익스트라를 사용하는 것이 이득
    • Floyd를 사용할경우 O(V^3)
    • 다익스트라 : O(ElgE)

문제 접근

• 시작 노드에서부터 나머지 노드까지의 거리 배열을 무한대값으로 초기화(dist 배열)

  • dist배열의 시작 노드값을 0으로 만듬

• 시작 노드 연결된 간선을 모두 우선순위 큐에 넣음

• 우선순위 큐가 가지고 있는 가장 작은 간선을 꺼냄

• 이 간선을 통할경우 기존의 거리 값보다 작아질때, 해당 노드에 연결된 간선을 우선순위 큐에 추가

• 위 과정을 우선순위 큐가 empty될때까지 반복

  
  

시간복잡도

• 모든 간선을 우선순위 큐에 넣음 : ElgE

  
  

대표예제 : 백준 1913 최소비용 구하기

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int inf = 1e8+10;
// 시작점에서부터 해당 노드까지의 거리
int dist[1010];
// 인접 간선 리스트
vector<pair<int, int>> adj[1010];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    // 거리 배열 무한값으로 초기화
    fill(dist, dist+1010, inf);
    
    int N,M; cin >> N >> M;
    while(M--) {
        int a,b,c; cin >> a >> b >> c;
        adj[a].push_back(make_pair(c,b));
    }
    int st, en; cin >> st >> en;
    
    // 시작 노드는 거리 0
    dist[st] = 0;
    
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(dist[st], st));
    
    while(!pq.empty()) {
        auto eq = pq.top(); pq.pop();
        int ec = eq.first;
        int ei = eq.second;
        
        // 같은 노드에 대한 간선 중, 이미 더 작은 값으로 업데이트 된경우
        if(dist[ei] != ec) continue;
        
        for(auto x : adj[ei]) {
            int nc = x.first;
            int ni = x.second;
            
            if(dist[ni] > ec + nc) {
                dist[ni] = ec + nc;
                pq.push(make_pair(dist[ni], ni));
            }
        }
    }
    
    cout << dist[en] << '\n';
    
    
    return 0;
}
 

문제 유형

• 다익스트라 경로 구하기 : https://www.acmicpc.net/problem/11779
• 거꾸로 다익스트라 : https://www.acmicpc.net/problem/1238
• 2차원 다익스트라 : https://www.acmicpc.net/problem/4485
• 한점 거치는 다익스트라 : https://www.acmicpc.net/problem/18223