다익스트라 알고리즘

이번에는 다익스트라 알고리즘을 공부해 봤다.

 

사실 다익스트라는 너무 잘 알려진 알고리즘이라 다른 여러 블로그들을 참고해서 

 

www.acmicpc.net/problem/1753

1753번: 최단경로

이 문제를 푸는 식으로 알아봤다.

 

const int INF = 1e9;
vector<pair<int, int>> ar[20001]; // ar[from].push_back({to, cost}) from -> to , 가중치
vector<int> d; // 거리값을 갱신해주는 배열

 

일단 기본적으로 가중치가 포함된 간선을 연결해줄 배열을 선언하고, 최단거리를 갱신해줄 배열도 필요하다.

 

void dijkstra(int s) {
	d[s] = 0;
	priority_queue<pair<int, int>> PQ; 
	PQ.push({ 0,s });
	while (!PQ.empty()) {
		int cur = PQ.top().second;
		int dist = -PQ.top().first;
		PQ.pop();
		if (d[cur] < dist) continue;
		for (auto i : ar[cur]) { 
			int nxt = i.first;		
			int nxtdist = dist + i.second; 
			if (nxtdist < d[nxt]) { 
				d[nxt] = nxtdist;
				PQ.push({ -nxtdist,nxt });
			}
		}
	}
}

 

기본적인 틀은 이렇다.

 

	d[s] = 0; //시작값은 0으로 초기화 후 시작
	priority_queue<pair<int, int>> PQ; //가중치, 현재 위치
	PQ.push({ 0,s });

 

처음 들어온 시작점은 0으로 초기화해주고 큐에 가중치, 현재 위치 순으로 넣어주는데

순서가 바뀌면 이상한 값을 건드려서 시간 초과가 난다.

 

		int cur = PQ.top().second;
		int dist = -PQ.top().first;
		//cout << "cur = " << cur << " dist = " << dist << '\n';

 

PQ의 두번째 값인 위치를 cur에 저장해주고 첫 번째 값인 가중치를 dist에 넣어준다.

이때 거리에 -를 붙혀서 최소 힙으로 바꿔줘야 한다.

여러 가중치들 값 중에서 가장 작은 값만을 사용해야 하니까.

 

		if (d[cur] < dist) continue;
		for (auto i : ar[cur]) { //i.first = 위치, i.seoncd = 가중치
			int nxt = i.first;		//여기서 여러 간선들의 가중치들을 구하지만..
			int nxtdist = dist + i.second; 
			if (nxtdist < d[nxt]) { //이 조건문에서 가장 최단거리만 갱신시켜줌
				d[nxt] = nxtdist;
				//printf("d[%d] = %d\n", nxt, d[nxt]);
				PQ.push({ -nxtdist,nxt });
			}
		}

 

주석 처리한 것과 같이 각 원소들의 연결점을 돌면서 다음 구간의 가중치와 위치를 저장해준다.

이후 if문에서 가장 작은 값만 갱신해주면 된다.

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int INF = 1e9;
vector<pair<int, int>> ar[20001]; // ar[from].push_back({to, cost}) from -> to , 가중치
vector<int> d; // 거리값을 갱신해주는 배열

void dijkstra(int s) {
	d[s] = 0; //시작값은 0으로 초기화 후 시작
	priority_queue<pair<int, int>> PQ; //가중치, 현재 위치
	PQ.push({ 0,s });
	while (!PQ.empty()) {
		int cur = PQ.top().second;
		int dist = -PQ.top().first;
		//cout << "cur = " << cur << " dist = " << dist << '\n';
		PQ.pop();
		if (d[cur] < dist) continue;
		for (auto i : ar[cur]) { //i.first = 위치, i.seoncd = 가중치
			int nxt = i.first;		//여기서 여러 간선들의 가중치들을 구하지만..
			int nxtdist = dist + i.second; 
			if (nxtdist < d[nxt]) { //이 조건문에서 가장 최단거리만 갱신시켜줌
				d[nxt] = nxtdist;
				//printf("d[%d] = %d\n", nxt, d[nxt]);
				PQ.push({ -nxtdist,nxt });
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	int v, e, k;

	cin >> v >> e >> k;
	d.resize(v + 1, INF);

	for (int i = 0; i < e; i++) {
		int x, y, z; cin >> x >> y >> z;
		ar[x].push_back({ y,z });
	}

	dijkstra(k);

	for (int i = 1; i <= v; i++) {
		if (d[i] == INF) cout << "INF" << ' ';
		else cout << d[i] << ' ';
	}
	cout << endl;

	return 0;
}

 

전체적인 소스코드는 이렇다.