[그래프] 다익스트라 알고리즘

서론

다익스트라 알고리즘은 한 정점에서 다른 모든 정점까지 가는 최단 거리와 경로를 구하는 알고리즘입니다.
그리디 기법을 기반으로 작동하며, 음수 간선이 있는 그래프에서는 사용할 수 없습니다.

작동 방식

처음에는 시작 정점까지의 거리는 0, 다른 모든 정점까지의 거리는 무한대로 초기화를 합니다. 이는 아직 방문하지 않았음을 의미합니다.

그 다음에는 모든 정점의 최단 경로를 확정짓기 전까지 아래 과정을 반복합니다.

현재 정점과 인접한 모든 정점들을 반복하면서 거리를 갱신시켜줍니다. 현재 정점까지의 최단 거리를 A, 현재 정점에서 인접한 정점 I을 잇는 간선의 가중치를 B, 지금까지 구한 I까지의 최단 거리를 C라고 할 때, A+B < C라면 I까지의 최단 거리를 A+B로 갱신해줍니다. 이 작업을 relexing이라고 합니다.
거리를 확정되지 않은 정점 중 가장 거리가 짧은 정점으로 이동한 뒤, 해당 정점의 최단 거리를 확정시킵니다. 이는 더 이상 그 정점의 최단 거리가 갱신될 일이 없음을 의미합니다.

O(V²) 구현

인접 리스트를 이용해 구현을 해봅시다.

#include <vector>
#include <utility>
#define x first
#define y second
using namespace std;

typedef pair<int, int> p;

vector<p> g[20001]; //인접 리스트
int dist[20001]={0}; //최단 거리
int chk[20001]={0}; //거리 확정 여부

//거리 초기화, 현재 정점은 시작 정점으로 초기화
for(int i=1; i<=v; i++) dist[i] = 1e9+7;
dist[start] = 0; chk[start] = 1;
now = start;

//V번 반복(모든 정점을 하나씩 거리 확정)
for(int aaa=0; aaa<v; aaa++){
    //인접한 모든 정점 방문
    for(auto i : g[u]){
    	int nxt = i.x;
    	int edgeCost = i.y;
        if(!chk[nxt]){
            if(dist[nxt] > dist[now] + edgeCost){
                dist[nxt] = dist[now] + edgeCost;
            }
        }
    }

    //최단 거리 확정
    chk[now] = 1;

    //7. 거리 미확정 정점 중, 출발점으로부터의 거리가 가장 작은 정점 선택
    int min = 1e9 + 7;
    for(int i=1; i<=v; i++){
        if(!chk[i]){
            if(dist[i] < min){
                min = dist[i];
                now = i;
            }
        }
    }
}

가장 가까운 정점을 찾는데 O(V)가 걸리는데, 이 행동을 모든 정점에 대해 수행하기 때문에 복잡도는 O(V²)이 나옵니다.

우선순위 큐를 도입하자

미확인 정점 중, 가장 가까운 정점을 찾는데 굳이 O(V)루프를 돌 이유가 없습니다. 우선순위 큐를 이용하면 그 작업을 O(lgV)만에 구행할 수 있습니다.
C++에서 제공해주는 우선순위 큐는 이진 힙으로 구현이 되었으며, 항상 top에 최대 혹은 최솟값을 갖고 있습니다. 삽입/삭제 명령은 모두 O(lgV)입니다.

작동 방식

처음에는 O(V²) 방식과 동일하게 출발 지점까지의 거리는 0, 나머지는 무한대로 초기화를 해줍니다.
그리고 우선순위 큐에는 {0, 출발점} 형태로 pair를 넣어줍니다. 이는 출발점까지의 거리가 0임을 나타냅니다.

이제 우선순위 큐가 빌 때 까지 아래 동작을 반복합니다.

큐에서 최솟값을 pop합니다. 그 pair는 어떤 정점과 그 정점까지의 거리를 갖고 있습니다. 각각 now와 cost라고 합시다. 만약 cost보다 이미 구해놓은 최단 거리가 더 짧으면 무시해줍니다.(continue)
now에서 갈 수 있는 모든 정점에 대해 최단 거리를 relaxing해줍니다. 이 때 최단 거리가 업데이트가 된다면 우선 순위 큐에 {해당 정점까지의 거리, 정점} 형태로 우선순위 큐에 넣어줍니다.

구현

C++에서 제공하는 우선순위 큐는 기본적으로 MaxHeap입니다. 즉, 최댓값을 top에 갖고 있습니다. 우리는 최솟값이 필요하므로 거리를 우선순위 큐에 넣을 때 -1을 곱해서 넣어줍시다.

#include <vector>
#include <utility>
#define x first
#define y second
using namespace std;

typedef pair<int, int> p;

vector<p> g[20001]; //인접 리스트
int dist[20001]={0}; //최단 거리

//초기화
for(int i=1; i<=b; i++) dist[i] = 1e9+7;

priority_queue<p> pq;
pq.push({0, start}); dist[start] = 0;

while(!pq.empty()){
	int now = pq.top().y;
	int cost = -pq.top().x; //-1을 곱해서 십입했으므로, 추출한 결과에 -1 곱함
	pq.pop();

	//이미 구한 거리가 더 짧으면 무시
	if(cost > dist[now]) continue;

	for(auto i : g[now]){
		int nxt = i.x;
		int nxtCost = cost + i.y; //현재까지의 거리 + 간선의 가중치
		if(nxtCost < dist[nxt]){
			nxtCost = dist[nxt];
			pq.push({-nxtCost, nxt}); //-1을 곱해서 삽입
		}
	}
}

경로 역추적

다익스트라 알고리즘을 이용하면 최단 거리와 그 경로까지 함께 구할 수 있습니다.
만약 now를 거쳐서 nxt로 가는 것이 최단 경로라면 par[nxt] = now 처럼 이전 정점을 저장해줄 수 있습니다.
경로를 추적하는 것은 도착 정점에서 시작해 par배열을 따라가면 됩니다.

#include <vector>
#include <utility>
#define x first
#define y second
using namespace std;

typedef pair<int, int> p;

vector<p> g[20001]; //인접 리스트
int dist[20001] = {0}; //최단 거리
int par[20001];

//초기화
for(int i=1; i<=v; i++) dist[i] = 1e9+7;
for(int i=1; i<=v; i++) par[i] = -1;

priority_queue<p> pq;
pq.push({0, start}); dist[start] = 0;

while(!pq.empty()){
	int now = pq.top().y;
	int cost = -pq.top().x; //-1을 곱해서 십입했으므로, 추출한 결과에 -1 곱함
	pq.pop();

	//이미 구한 거리가 더 짧으면 무시
	if(cost > dist[now]) continue;

	for(auto i : g[now]){
		int nxt = i.x;
		int nxtCost = cost + i.y; //현재까지의 거리 + 간선의 가중치
		if(nxtCost < dist[nxt]){
			nxtCost = dist[nxt];
			pq.push({-nxtCost, nxt}); //-1을 곱해서 삽입
			par[nxt] = now;
		}
	}
}

E개의 간선이 pq에 들어가며, 힙 트리의 높이는 O(logV)이므로 시간 복잡도는 O(ElogV)입니다.

서론

작동 방식

O(V2) 구현

우선순위 큐를 도입하자

작동 방식

구현

경로 역추적

추천 문제

O(V²) 구현