다익스트라(dijkstra)

한 정점에서 모든 정점으로 최단 경로를 구하는 알고리즘

 

아래는 priority_queue를 사용한 dijkstra 구현

void dijkstra(int arr[MAX_N][MAX_N], int start, int dist[MAX_N]) {
	priority_queue< pair<int, int>> pq;
    
    for(int i = 0; i < MAX_N; i++){
    	dist[i] = INF;
    }
    
    dist[start] = 0;
    pq.push({0, start});
    
    while(!pq.empty()){
    	int curr_dist = -pq.top().first;
        int curr_node = pq.top().second;
        pq.pop();
        
        if(curr_dist != dist[curr_node]) continue;
        
        for(int i = 0; i < MAX_N; i++){
        	int next_dist = curr_dist + arr[curr_node][i];
            
            if(next_dist < dist[i]){
            	dist[i] = next_dist;
                pq.push({ -next_dist, i });
            }
        }
    }
}

 

 

기본1: https://www.acmicpc.net/problem/1753

기본2: https://www.acmicpc.net/problem/11779

 

응용1: https://www.acmicpc.net/problem/1162

응용2: https://www.acmicpc.net/problem/1854