Dijkstra Algorithm (다익스트라 알고리즘)

Dijkstra Algorithm

먼저 다익스트라 알고리즘은 하나의 시작점으로부터 다른 모든 정점까지의 최단거리를 구하는 알고리즘입니다

(Greedy 기반으로 최적의 경로를 탐색)

 

※ Greedy란 탐욕 알고리즘으로 매번 주어진 상황에서 가장 최적의 경로를 선택함으로써 만들어가는 탐색 방법입니다.

 

다익스트라 알고리즘은 학부 알고리즘 수업에서 반드시 다루는 알고리즘이며 네트워크 같은 곳에서도 종종 쓰이기 때문에 이름과 그 목적만큼은 유명합니다.

 

참고로 길찾기 알고리즘의 대표적인 예시로 A*(astar) 알고리즘이 있습니다. 대표적으로 네비게이션에서의 길찾기처럼 100% 정확한 최단거리를 내지 않아도 되고, 또 정점의 개수가 너무 많아 현실적으로 다익스트라 알고리즘을 활용하기 힘들경우에 사용되는 근사 알고리즘입니다.

 

 

-동작 과정

노드	1	2	3	4
비용	Inf	Inf	Inf	Inf

위와 같이 처음 시작 노드를 3으로 가정하고 알고리즘을 적용하겠습니다.

먼저 가장 처음 각각의 노드에서 이동할 수 있는 비용은 모두 Infinity로 설정합니다.

단, 시작지점인 3번 노드의 비용은 자기자신의 거리이므로 0으로 표기해도 좋습니다

 

 

다음 3번노드에서 이동 가능한 2번과 4번 노드의 비용을 각각 현재 배열에 저장된 값과 비교하여 최솟값을 선택합니다.

min(arr[2],12) 와 min(arr[4],5)를 각각 비교하면 현재 배열에 저장된 값이 Infinity 값이기 때문에 아래와 같이 배열을 수정할 수 있습니다.

 

노드	1	2	3	4
비용	Inf	12	0	5

 

그리고 2번 노드와 4번 노드 중 최소 비용이 걸리는 4번 노드로 이동 후 같은 작업을 반복합니다.

4번 노드의 경우 1번 노드와 2번 노드로 이동할 수 있기 때문에 min(arr[1],arr[4]+1) 과 min(arr[2],arr[4]+7)을 통해 배열을 수정합니다.

노드	1	2	3	4
비용	6	12	0	5

위와 2번 노드로 이동하는 비용은 12로 같으므로 변화가 없으며 1번 노드로 가는 비용은 무한대보다 6이 더 낮은 값이기 때문에 최솟값으로 6을 넣어줍니다.

마찬가질로 1번 노드로 이동 후 같은 작업을 반복합니다. 이때 min(arr[1]+3, arr[2])를 비교하고

노드	1	2	3	4
비용	6	9	0	5

결과적으로 2번 노드에 최소비용 값이 수정 되는 것을 알 수 있습니다.

마찬가지로 2번노드로 이동 후 같은 작업을 반복하는데 이 때 2번 노드에서 이동할 수 없는 화살표가 없기 때문에 작업은 더 이상 일어나지 않습니다.

또한 모든 노드를 방문하면 다익스트라 알고리즘은 종료되므로 위 정리된 최소비용배열을 구함으로써 다익스트라 알고리즘이 종료됩니다.

 

 

다익스트라 알고리즘에서는 매번 가장 가까운 정점을 뽑아내야 합니다. 원소의 추가가 가능하고 최솟값의 확인 및 삭제가 효율적인 자료구조는 힙 아니면 우선순위 큐 입니다.

 

우선순위 큐를 이용한 다익스트라 알고리즘

1. 우선순위 큐에 (0,시작점)을 추가
2. 우선순위 큐에서 거리가 가장 작은 원소를 선택, 해당 거리가 최단 거리 테이블에 있는 값과 다른 경우 3번 과정을 수행하지 않고 넘어간다
3. 원소가 가리키는 정점을 v라고 할 때, v와 이웃한 정점들에 대해 최단 거리 테이블 값보다 v를 거쳐가는 것이 더 작은 값을 가질 경우 최단 거리 테이블의 값을 갱신하고 우선순위 큐에 (거리, 이웃한 정점의 번호)를 추가
4. 우선순위 큐가 빌 때까지 2,3번 과정을 반복수행

 

 

https://www.acmicpc.net/problem/1753

1753번: 최단경로

코드 바로 보여드리고 설명을 뒤에 붙이겠습니다.

#include <bits/stdc++.h>
using namespace std;

#define X first
#define Y second

int v,e,st;

//(비용, 정점 번호)
vector<pair<int, int>> adj[20005];
const int INF = 1e9+10;
int d[20005]; //최단 거리 테이블
int main(){
	ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>e>>st;
    fill(d,d+v+1,INF);
    
    while(e--){
    	int u,v,w;
        cin >> u >> v >> w;
        adj[u].push_back({w,v});
    }
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    d[st]=0;
    //우선순위 큐에 (0, 시작점) 추가
    pq.push({d[st],st});
    while(!pq.empty()){
    	auto cur = pq.top(); pq.pop();
        if(d[cur.Y] != cur.X) continue;
        for(auto nxt: adj[cur.Y]) {
        	if(d[nxt.Y] <= d[cur.Y]+nxt.X) continue;
            d[nxt.Y] = d[cur.Y] + nxt.X;
            pq.push({d[nxt.Y],nxt.Y});
        }
    }
    for (int i=1; i <= v; i++){
    	if(d[i] == INF) cout << "INF\n";
        else cout << d[i] << "\n";
    }

}

pair와 비교 함수를 별도로 선언을 안하고 간선이나 우선순위 큐의 우너소를 (거리, 정점 번호) 순서로 배치했습니다.

그리고 우선순위 큐는 27~29번째 줄처럼 선언해서 min heap으로 뒀습니다. 결국 33번째 줄부터가 논리의 핵심입니다.

33번째 줄은 cur을 거쳐가는 것이 더 작은 값을 가질 경우, d[nxt.Y]를 갱신하고 우선순위 큐에 (거리, nxt.Y)를 추가하는 의미로 코드를 뒀습니다.

 

13번째 줄인 d는 최단거리 테이블을 의미했습니다. 

 

한편으로 cur.X,cur.Y,nxt.X,nxt.Y 값이 어떤 걸 의미하는지 헷갈릴 수 있기 때문에 cur_idx = cur.Y, cur_dist = cur.X 이런 식으로 별도의 변수를 두고 코드를 작성해도 좋습니다.

 

한편으로 문제의 조건에서 서로 다른 주 정점 사이에 여러 개의 간선이 존재할 수 있다고 했는데도 그에 대한 처리가 없는 것을 확인할 수 있는데, 별도로 처리를 하지 않아도 어차피 다익스트라 알고리즘 과정을 진행하다보면 비용이 더 큰 간선은 알아서 반영이 되지 않기 때문입니다