[PS일지]백준 1753번 최단경로, 다익스트라기초

 

DFS, BFS를 배운 뒤 최단경로관련 알고리즘을 배우기 시작하게 되었다.

다익스트라, 벨만-포드, 플로이드-와셜 등

가중치가 없었을 때는 BFS의 아주 좋은 성질로 쉽게 풀 수 있었지만, 

가중치(돈, 거리, 시간 등등)가 있는 그래프에서는 BFS를 적용하기 힘들다.

 

가중치가 있는 곳에서 최단경로를 찾기위해 BFS와 비슷한 방식을 사용하는 알고리즘이

있는데, 그것이

다익스트라 알고리즘이다.

 

기초적인 연습문제를 풀기 전에 다익스트라 알고리즘에 대해 배워보자

 

 다익스트라 알고리즘은 네덜란드의 전산학자 에츠허르 데이크스트라가 고안한 알고리즘이다

이분은 튜링상까지 받은 매우 유명한 분이다.(수학에서 필즈상으로 보면 된다.)

 

BFS에서 인접한 정점을 모두 방문하듯이 다익스트라 알고리즘은 우선순위큐(priority queue)를 이용해서 인접한 정점을 방문하는 경우가 많다.(visit배열을 쓰는 경우도 있다)

 

다익스트라 알고리즘은 단일점 알고리즘으로, 한 점에서 다른 점으로의 최단거리를 계산한다.

 

동작과정을 보자

1. 시작지점과 0을 pair객체 형태로 0, 시작지점으로 우선순위 큐에 저장한다.

2. 0을 저장하는 이유는, 현재까지 알려진 시작지점부터 x지점까지의 최단 경로를 저장하기 때문이다.

이 때문에, 우선순위 큐에는 최단경로부터 뽑히게 된다.

3. 우선순위 큐에서 맨 앞 원소를 빼내 변수에 저장한다.(각각, 시작위치부터 x위치의 현재까지 알려진 최단경로(저장하는 변수 이름을 z라 하자), x이다.)

4. x와 인접한 정점 y를 찾는다. (BFS과정과 비슷하다)

5. dist배열에는 dist[a] = 시작위치부터 정점 a에서 현재까지 알려진 최단경로가 저장된다., 아직 모를때는 INF(무한)으로 초기화되게 된다. 4번에서 찾은 정점 y에 대해 dist[y]보다 z+w[y]가 작다면 dist[y]를 z+w[y]로 갱신한뒤 우선순위 큐에 

(z+w[y], y)를 pair 객체로 만들어 넣는다. 만약 4번에서 찾은 정점 y에 대해 dist[y]보다 z+w[y]가 크면 continue 문을 통해 아래에 있는 코드를 무시한다.

(BFS에서 visit가 true일때 무시하는 것과 비슷하다)

 (w배열은 가중치를 저장하는 배열이다)

6. 3~5과정을 우선순위큐가 빌때까지 반복한다.

7. dist배열에 시작점으로부터 모든 최단경로가 저장된다.

 

다익스트라 알고리즘의 정당성은 귀류법으로 증명가능하다.

 

그럼 다익스트라 알고리즘을 백준 문제 1753번에 적용해보자

 

간단한 문제이다.

정점이 연결되었는지를 백터배열로 만들고(공간복잡도, 시간복잡도를 위해)

다익스트라를 해주면 된다.

 

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
#define INF 4000000
int v, e, k, dist[20000];
vector<pair<int, int>>state[20000];
priority_queue<pair<int, int>>q;
void dik(int x){
	q.push(make_pair(0, x));
	while(!q.empty()){
		int a = -q.top().first, b = q.top().second;
		q.pop();
		if(dist[b] < a)continue;
		for(int i = 0; i < state[b].size(); i++){
			int temp = state[b][i].second, index = state[b][i].first;
			if(temp+a < dist[index]){
				dist[index] = temp+a;
				q.push(make_pair(-temp-a, index));
			}
		}
	}
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int i, a, b, w;
	cin >> v >> e;
	cin >> k;
	for(i = 0; i < e; i++){
		cin >> a >> b >> w;
		state[a-1].push_back(make_pair(b-1, w));
	}
	for(i = 0; i < v; i++)if(i != k-1)dist[i] = INF;
	dik(k-1);
	for(i = 0; i < v; i++){
		if(dist[i] == INF)cout << "INF\n";
		else cout << dist[i] << "\n";
	}
}

 

공감,댓글은 사랑입니다

코딩 초보를 귀여워해주세요!