[Algorithm] 다익스트라 알고리즘

Reference

• 바킹독님 [실전 알고리즘] 0x1D강 - 다익스트라 알고리즘

01. 다익스트라 알고리즘

✨ 하나의 시작점부터 다른 모든 정점까지의 최단거리를 구하는 알고리즘 ( single-source )

• 다른 모든 정점에서 하나의 도착점까지의 최단 거리를 구하는 single-destination 문제에 모두 적용 가능
• 참고 간선의 가중치가 음수인 경우, 적용이 불가함
  • 간선의 가중치가 음수를 포함하는 경우, 벨만-포드 알고리즘을 생각해보자.

다익스트라 알고리즘은 start vertex s 로부터 최단 경로의 길이를 이미 알아낸 노드들의 집합 ${S=\{s\}}$ 를 이용한다.

• ${u \notin S}$ 인 각 vertex ${u}$ 에 대해 ${d(u)}$는 이미 ${S}$에 속한 vertex만 거쳐 ${s \rightarrow u}$까지 가는 최단 경로

02. 구현

다익스트라(Dijkstra) 알고리즘은 구현 방법에 따라 최악의 경우 시간복잡도가 ${O(VE), O(V^2+E) , O(VlogV)}$ 인 알고리즘이다.

• ${O(VE)}$ : 어떤 정점과 인접한 정점들을 매번 모두 확인하면서 가장 짧은 거리에 있는 정점의 값을 갱신하는 방법
  • ${E}$ 의 값이 ${V}$ 보다 한참 작을 때 유용한 방법
• ${O(V^2+E)}$ : 어떤 정점과 인접한 정점들까지의 거리를 모두 계산해놓고 가장 짧은 거리에 있는 정점의 값을 갱신하는 방법
• ${O(VlogV)}$ : 우선 순위 큐를 활용하는 방법

1 ) $O(V^2 + E)$ : 인접 정점까지의 거리를 계산해두고 갱신하는 방법

• STEP 1 각 정점까지의 거리를 $\infin$ 로 초기화한다.
• STEP 2 매 단계마다 갈 수 있는 정점 중 거리가 가장 가까운 정점을 구해 거리를 확정하는 방식으로 동작한다.

#include <vector> 
#include <utility>
#include <algorithm>

// 인접 행렬 
// (거리, 정점 번호 index)
std::vector<std::pair<int,int>> adj[20005]; 
// start vertex로 부터의 최단 거리를 저장하는 배열
int dist[20005]; 
// 최단 거리 계산이 완료 되었는지 확인하기 위한 배열 
bool fix[20005];

void dijkstra_naive(int startV){
	
	d[startV] = 0 ;
	
    while(true){
    	// 최단거리를 갱신할 index 
    	int idx = -1; 
        for(int i = 1 ; i <= V ; ++i){
        	// 이미 최단거리가 확정된 index
        	if(true == fix[i]) continue;
            // 갱신할 index가 아직 정해지지 않은 경우
            else if(-1 == idx) idx = i ; 
            // 가장 짧은 거리를 가지는 정점을 찾아야 하므로 index 갱신 
            else if(d[i] < d[idx]) idx = i;
        }
        
        // 더이상 갱신할 것이 없으면 끝 
        if( -1 == idx || INF == d[idx] ) break;
        
        fix[idx] = true; 
        // 갱신한 정점으로부터 인접한 정점들을 확인한다. 
        for( auto nxt : adj[idx]){
        	d[nxt.second] = min( d[nxt.second], nxt.first + d[idx])
        }
    }
}

2 ) ${O(VlogV)}$ : 우선 순위 큐를 이용하는 방법

• STEP 1 우선 순위 큐에 (0, 시작점) 을 추가한다.
• STEP 2 우선 순위 큐에서 거리 값이 가장 작은 원소를 선택한다.
  • 해당 거리가 최단 거리 테이블에 있는 값과 다를 경우, 최단 거리가 아직 구해지지 않은 것이므로 다음 단계를 진행하지 않고 STEP 2로 돌아간다.
• STEP 3 선택된 원소가 가리키는 정점을 ${v}$ 라고 할 때, ${v}$와 이웃한 정점들에 대해 최단 거리 테이블에 있는 값보다 ${v}$ 를 거쳐갈 때의 값이 더 작을 경우, 최단 거리 테이블의 값을 갱신한 후 (거리, 인접 정점 번호) 를 큐에 추가한다.
• STEP 4 큐가 빌 때 까지 STEP 2, STEP 3 반복

// 우선 순위 큐 (최소 힙)
std::priority_queue<std::pair<int,int>, std::greater<std::pair<int,int>> dijkstraPq;

int dist[20005];

void dijkstra(int st){
	dist[st] = 0 ; 
    dijkstraPq.push(std::make_pair(dist[st], st));
    
    while( false == dijkstraPq.empty() ){
    	std::pair curPair = dijkstra.top(); dijkstra.pop();
        const int & curV = curPair.second;
        const int & curDist = curPair.first; // dist[curV] 와 같은 값
        
        // 아직 최단 거리가 갱신되지 않은 vertex 이므로 priority queue 에서만 빼고 지나간다. 
        if( curDist != dist[curV] ) continue;
        
        // 인접 노드를 돌면서 갱신할 값을 찾는다.
        for( auto nxt: adj[curV] ){
        	const int & nextV = nxt.second;
            const int & nextDist = nxt.first;
        	
            if(curDist + nextDist > dist[nextV]) continue ; 
            // 최단 거리 갱신
            dist[nextV] = curDist + nextDist; 
            // priority queue 에 추가
            dijkstra_pq.push(std::make_pair(nextV, dist[nextV]));
            
        }
        
    }
}