다익스트라 알고리즘

최단 경로 문제는 그래프에서 두 정점 사이의 가중치 합이 최소가 되는 경로의 길이를 찾는 문제입니다.

문제를 풀기 전에 아래의 상황을 고려해야 합니다.

 

1. 음수 가중치가 있는가 

2. 시작점이 주어지는가

 

최단 경로 알고리즘에는 크게 다익스트라 알고리즘, 벨만-포드 알고리즘, 플로이드-와샬 알고리즘이 있습니다.

위에서 언급한 조건을 생각하여 어떤 알고리즘을 사용할지 선택해야하는데, 동일한 알고리즘이라도 구현 방식에 따라 알고리즘 성능이 좌우됩니다.

---

먼저, 1번을 고려해봅니다.

음수 가중치를 거쳐간다면 경로의 길이가 짧아지기 때문에 최단 경로를 결정할 때, 매력적인 선택지입니다.

 

그러나, 음수 가중치를 가진 경로가 사이클을 이루는 경우(한바퀴 돌았을 때의 합이 음수)가 있다면, -INF로 경로의 길이가 발산할 수 있기에 최단 경로가 제대로 정의되지 않습니다.

 

이러한 점을 고려할 때, 그래프는 세 종류로 나눌 수 있습니다.

 

1-1. 양수 가중치로만 이루어진 경우

1-2. 음수 가중치가 있지만 사이클을 이루진 않은 경우

1-3. 음수 가중치가 있고, 음수 사이클도 형성된 경우

 

일단은 다익스트라 알고리즘은 음수 가중치가 있는 경우 사용할 수 없고, 벨만-포드 알고리즘과 플로이드-와샬 알고리즘은 음수 가중치가 있는 경우에도 사용이 가능하다고 알아두는 것이 좋을 것 같습니다.

 

 

2번을 고려해봅니다.

다익스트라 알고리즘과 벨만-포드 알고리즘은 단일 시작점으로부터 각 정점 별 최단 경로의 길이를 알 수 있습니다.

 

반면에, 플로이드-와샬 알고리즘은 그래프 상의 모든 쌍에 대한 최단 경로를 알 수 있습니다.

 

물론 단일 시작점 알고리즘을 여러 번 반복하여 모든 쌍에 대한 최단 경로를 알아낼 수도 있지만,

플로이드-와샬 알고리즘은 그보다 더 간단하게 구현이 가능하다는 장점이 있습니다.

 

최단 경로 알고리즘들의 특징을 간단히 정리하자면 아래와 같은 표로 나타낼 수 있습니다.

 

	음수 가중치가 있어도 사용할 수 있는가	시작점이 정해져 있는가
다익스트라 알고리즘	x	o
벨만-포드 알고리즘	o	o
플로이드-와샬 알고리즘	o	x

따라서, 문제를 보고 위에 적힌 알고리즘 중 어떤 것을 사용할지 판단할 수 있어야 합니다.

 

이 포스팅에선 다익스트라 알고리즘에 대하여 알아볼 것입니다.

---

그래프에서 시작점 1에서 각 정점별 최단 경로의 길이를 다익스트라로 알아보겠습니다.

 

먼저, 시작점 1을 제외한 모든 정점의 최단 경로 길이를 Max 값으로 초기화 시켜줍니다. 시작점의 경로 길이는 0입니다.

 

시작점을 우선순위 큐에 넣겠습니다. 

 

큐에서 하나를 꺼내고 (비용이 0인 1번 노드), 꺼낸 노드에 인접한 정점을 간선을 타고 접근해보겠습니다.

1번 노드까지의 비용 + 1번에서 3번으로 가는 비용 = 4 가 Max보다 작으니 3번 노드까지의 비용은 4가 됩니다.

2번 노드까지의 비용 + 1번에서 2번으로 가는 비용 = 5 가 Max보다 작으니 2번 노드까지의 비용은 5가 됩니다.

 

비용이 갱신되면 우선순위 큐에 노드 번호와 비용을 함께 넣습니다.

큐에는 비용이 4인 3번 노드와 비용이 5인 2번 노드가 존재합니다.

우선순위 큐에서 비용이 작은 것부터 꺼냅니다.

비용이 4인 3번 노드가 꺼내질 것이고 3번 노드에 인접한 정점을 탐색하기 위해 간선을 살펴봅니다.

 

3번 노드까지의 비용 + 3번에서 4번으로 가는 비용 = 10 가 Max보다 작으니 4번 노드까지의 비용은 10이 됩니다.

3번 노드까지의 비용 + 3번에서 5번으로 가는 비용 = 11 가 Max보다 작으니 5번 노드까지의 비용은 11이 됩니다.

3번 노드까지의 비용 + 3번에서 6번으로 가는 비용 = 12 가 Max보다 작으니 6번 노드까지의 비용은 12가 됩니다.

 

큐에는 비용이 5인 2번 노드, 비용이 10인 4번 노드, 비용이 11인 5번 노드, 비용이 12인 6번 노드가 존재합니다.

우선순위 큐에서 비용이 작은 것부터 꺼냅니다.

비용이 5인 2번 노드가 꺼내질 것이고 2번 노드에 인접한 정점을 탐색하기 위해 간선을 살펴봅니다.

 

2번 노드까지의 비용 + 2번에서 3번으로 가는 비용 = 10 이 4보다 크니 갱신이 일어나지 않습니다.

2번 노드까지의 비용 + 2번에서 4번으로 가는 비용 = 8 이 10보다 작으니 4번 노드까지의 비용은 8이 됩니다.

 

큐에는 비용이 8인 4번 노드, 비용이 10인 4번 노드, 비용이 11인 5번 노드, 비용이 12인 6번 노드가 존재합니다.

 

 

우선순위 큐에서 비용이 작은 것부터 꺼냅니다.

비용이 8인 4번 노드가 꺼내질 것이고 4번 노드에 인접한 정점을 탐색하기 위해 간선을 살펴봅니다.

 

4번 노드까지의 비용 + 4번에서 5번으로 가는 비용 = 10 이 11보다 작으니 5번 노드까지의 비용은 10이 됩니다.

4번 노드까지의 비용 + 4번에서 6번으로 가는 비용 = 9 가 12보다 작으니 6번 노드까지의 비용은 9가 됩니다.

 

큐에는 비용이 9인 6번 노드, 비용이 10인 5번 노드, 비용이 10인 4번 노드, 비용이 11인 5번 노드, 비용이 12인 6번 노드가 존재합니다.

 

우선순위 큐에서 비용이 작은 것부터 꺼냅니다.

비용이 9인 6번 노드가 꺼내질 것이고 6번 노드에 인접한 정점을 탐색하기 위해 간선을 살펴봅니다.

 

6번 노드까지의 비용 + 6번에서 7번으로 가는 비용 = 11이 Max보다 작으니 7번 노드까지의 비용은 11이 됩니다.

 

큐에는 비용이 10인 5번 노드, 비용이 10인 4번 노드, 비용이 11인 7번 노드, 비용이 11인 5번노드, 비용이 12인 6번 노드가 존재합니다.

 

우선순위 큐에서 비용이 작은 것부터 꺼냅니다.

비용이 10인 5번 노드가 꺼내질 것이고 5번 노드에 인접한 정점을 탐색하기 위해 간선을 살펴봅니다.

 

5번 노드까지의 비용 + 5번에서 6번으로 가는 비용 = 11이 9보다 크니 갱신이 일어나지 않습니다.

5번 노드까지의 비용 + 5번에서 7번으로 가는 비용 = 12가 11보다 크니 갱신이 일어나지 않습니다.

 

큐에는 비용이 10인 4번 노드, 비용이 11인 7번 노드, 비용이 11인 5번 노드, 비용이 12인 6번 노드가 존재합니다.

그러나 현재 저장된 비용이 큐에 기록된 비용보다 작기 때문에 갱신은 일어나지 않으며 큐가 비워지고 끝이 납니다.

 

 

이렇게 다익스트라 알고리즘으로 시작점 1에 대하여 모든 정점에 대한 최단 경로의 길이를 구할 수 있었습니다.

 

이를 소스코드로 구현해봅니다.

---

int V,E,u,v,w;

vector <pair<int, int>> adj[V_Max];
//메인함수에서 간선을 저장할 벡터배열을 만들어놓습니다.
//adj[u]벡터의 첫번째에는 v가, 두번째에는 u에서 v로 이동할 때의 w가 저장됩니다.

vector<int> dijkstra(int src) {

	priority_queue <pair<int, int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;
    //greater를 사용하여 나중에 큐에서 원소를 뽑을 때, 가중치가 낮은 것부터 뽑히도록 합니다.
    
	vector<int> dist(V, INT_MAX);
    //도착점 별 초기 경로의 길이는 모두 큰값으로 초기화를 해둡니다. 
    
	dist[src] = 0;
    //시작점에서 시작점으로의 최단경로 길이는 당연히 0입니다.
    
	pq.push({ 0,src });
    //pair간 정렬은 첫번째 원소를 비교하기 때문에 비교할 대상인 가중치를 pair의 첫번째에 넣습니다.
    //시작점에서 시작점은 거리가 0이기에, 비용이 0인 시작점src를 큐에 넣습니다.
    
	while (pq.empty() != true) {
    //큐가 비워질 때까지 반복해줍니다.
    
		int cost = pq.top().first;
        //큐에서 가중치가 가장 낮은 가중치를 저장합니다.
        
		int here = pq.top().second;
        //큐에서 가중치가 가장 낮은 정점의 번호를 저장합니다.
		
        pq.pop();
        //가중치가 가장 낮은 정점를 제거합니다.
        
		if (dist[here] < cost) continue;
		//큐에서 뽑은 정점의 가중치가 이미 저장된 비용보다 크다면 넘어갑니다.
        
        for (int i = 0;i < (int)adj[here].size();i++) {
        //큐에서 뽑은 정점에 붙어있는 간선들을 체크합니다.
        
			int there = adj[here][i].first;
            //큐에서 뽑은 정점에서 이동할 정점의 번호를 저장합니다.
            
			int nextdist = cost + adj[here][i].second;
			//큐에서 뽑은 정점에서 다른 정점으로 넘어갔을 때의 총 비용을 저장합니다.
            
            if (dist[there] > nextdist) {
            //방금 계산한 비용이 이미 저장된 비용보다 작다면
            
				dist[there] = nextdist;
                //비용을 새로 갱신하고
                
				pq.push({ nextdist,there });
               	//해당비용과 넘어간 정점을 큐에 넣습니다. 
               
			}
		}
	}
	return dist;
    //시작점src에서 다른 정점까지의 최단경로비용이 계산된 벡터를 반환합니다.
}

---

 

우선순위 큐를 이용한 다익스트라 알고리즘의 시간복잡도

 

특정 정점에 인접한 정점을 탐색하는 것은 안타깝게도 무료가 아닙니다.

인접한 정점을 연결하는 간선만큼 방문을 해봐야 한다는 의미이므로, 각각의 정점에 붙어있는 각각의 간선들을 고려했을 때, 이 과정에서 O(|E|) 만큼의 시간이 소요됩니다.

 

또한, 최악의 경우 간선을 검사할 때마다 최단경로의 길이가 갱신되어 큐에 모든 간선이 들어갈 수 있습니다 (=O|E|).

큐를 삭제하거나 삽입하는 것은 O(lg|E|) 의 시간이 걸린다고 알려져 있기 때문에 (|E|lg|E|) 의 시간이 걸립니다.

 

즉, O(|E|lg|E|+|E|) = O(|E|lg|E|) 의 시간복잡도를 갖는다고 할 수 있습니다.

 

시간복잡도를 간선의 개수 뿐 아니라 정점의 개수에도 연관을 짓는다면

통상 간선의 개수가 정점의 개수 제곱보다 작기 때문에 O(lg|E|)= O(lg|V|)가 성립하고

//모든 정점이 서로 간선으로 연결되어있을 때의 간선의 개수는 V*(V-1) 개 입니다.

우선순위 큐를 이용한 다익스트라 알고리즘의 시간 복잡도는 O(|E|lg|E|)=O(|E|lg|V|) 라고 할 수 있습니다.

---

우선순위 큐를 사용하지 않는 다익스트라 알고리즘

 

알고리즘 동작 중, 비용이 갱신됨에 따라 우선순위 큐에 있던 비용이 큰 정점이 쓸모없게 되어버린 경우가 있었습니다.

탐색할 간선의 개수가 정점의 개수에 비하여 월등히 커질 때, 이러한 경우가 빈번히 발생합니다.

시간 복잡도를 생각했을 때, 필요없는 정점 큐에 많이 쌓이는 것은 좋은 현상은 아닙니다.

 

이런 경우는 아직 방문하지 않은 정점의 최단 경로 비용을 반복문을 이용하여 찾는 것이 빠릅니다.

 

int V, E, u, v, w;
vector <pair<int, int>> adj[V];
vector<int> dijkstra(int src) {
    vector<int> dist(V, INT_MAX);
    vector <bool> visit(V, false);
    dist[src] = 0;
    visit[src] = true;
    while (true) {
        int closest = INT_MAX, here;
        for (int i = 0;i < V;i++)
            if (dist[i] < closest && visit[i] != true) {
                here = i;
                closest = dist[i];
            }
        if (closest == INT_MAX) break;
        visit[here] = true;
        for (int i = 0;i < (int)adj[here].size();i++) {
            int there = adj[here][i].first;
            if (visit[there] == true) continue;
            int nextdist = dist[here] + adj[here][i].second;
            dist[there] = min(dist[there], nextdist);
        }
    }
    return dist;
}

---

연습문제

 

2020/08/26 - [백준] - 백준 소스코드 [C++] 1753 최단경로

2020/08/30 - [백준] - 백준 소스코드 [C++] 1504 특정한 최단 경로

2020/09/01 - [백준] - 백준 소스코드 [C++] 11779 최소비용 구하기 2

 

최단 경로 알고리즘 중 다익스트라 알고리즘에 대한 포스팅이었습니다.

 

오타 지적과 조언은 언제나 환영입니다.