다익스트라

다익스트라 알고리즘은 그래프에서 여러개의 노드가 있을때, 특정한 노드에서 출발하여 다른 노드로가는 최단 경로를 구하는 알고리즘이다.

 

다익스트라 동작 방식은 다음과 같다.

 

1. 출발노드를 설정한다.

2. 최단거리 테이블을 초기화한다.

3. 방문하지 않는 노드중에서 최단거리가 가장 짧은 노드를 선택한다.

4. 해당노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단거리 갱신

5. 위 과정에서 3 4 반복.

 

다익스트라를 구현하는 방법은 두가지가있는데,

 

하나는 1차원 리스트를 순차탐색하면서 구현하는 방법이고 

두번째는 힙(우선순위큐)를 이용하여 구현하는 방법이다. 

 

첫번째 방법의경우 O(V^2) 의 시간복잡도를 가지지만 두번째는 O(ElogV) 의 시간복잡도를 가진다.

 

아래는 우선순위큐를 이용하여 다익스트라를 구현한 코드이다.

 

#include <iostream>
#include <vector>
#include <queue>
#define INF 1e9
using namespace std;
int n, m, start;
vector<pair<int, int> > graph[100001];
int cost_table[100001];
struct compare{
	bool operator()(pair<int, int>a, pair<int, int>b){
		return a.second> b.second;
	}
};
void dijkstra(int start) {
    priority_queue<pair<int, int>, vector<pair<int,int> > ,compare > pq;
    
    pq.push({start, 0});
    cost_table[start] = 0;
    while (!pq.empty()) {
        int now = pq.top().first; // 현재 노드
        int dist = pq.top().second; // 현재 노드까지 비용
        pq.pop();
        if (cost_table[now] < dist) continue;
        for (int i = 0; i < graph[now].size(); i++) {
            int cost = dist + graph[now][i].second;
            int nextV =  graph[now][i].first;
            
            if (cost < cost_table[nextV]) {
                cost_table[nextV] = cost;
                pq.push({nextV,cost});
            }
        }
    }
}
int main(void) {
    cin >> n >> m >> start;
    
    for (int i = 0; i < m; i++) {
        int v1 , v2 , cost;
        cin >> v1 >> v2 >> cost;
        graph[v1].push_back( {v2, cost} );
    }

    fill_n(cost_table, 100001, INF);
    
    dijkstra(start);

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