<Baekjoon> #1753 Dijkstra_최단경로 c++

Google 아니고 Joogle·2022년 3월 29일
0

Baekjoon

목록 보기
45/47
post-thumbnail

#1753 최단 경로

💡Dijkstra Algorithm

  • 단일 시작점 최단 경로 알고리즘으로, 시작 정점 s에서부터 다른 정점들까지의 최단 거리를 계산

  • 우선 순위 큐 사용

  1. 우선 순위 큐에 지금까지 찾아낸 해당 정점까지의 최단 거리, 정점의 번호를쌍으로 넣음
    priority_queue <pair<int, int>> pq;
  2. 정점까지의 최단 거리를 기준으로 정점을 정렬함으로써, 아직 방문하지 않은 정점 중 시작점으로부터의 거리가 가장 가까운 점을 찾음
    pq.push({ -nextDist, next });
    // 거리를 음수 값으로 넣어주어 거리가 짧을 수록 우선 순위가 높게 정렬한다
  3. 각 정점까지의 최단 경로는 갱신되는데, queue에서 꺼낸 거리의 값보다 더 짧은 경로를 이미 알고 있다면 이 값은 무시한다
int V;

//vertex number, weight
vector<pair<int, int>> adj[MAX];

vector<int> dijkstra(int src) {
	vector<int> dist(V, INF);
	dist[src] = 0;
	priority_queue <pair<int, int>> pq;
	pq.push({ 0, src }); // distance, vertex number

	while (!pq.empty()) {
		int cost = -pq.top().first;
		int cur = pq.top().second;
		pq.pop();

		//지금 꺼낸 것보다 더 짧은 경로를 알고 있다면 무시
		if (dist[cur] < cost) continue;
		
		for (int i = 0; i < adj[cur].size(); i++) {
			int next = adj[cur][i].first; // vertex number adj with cur
			int nextDist = cost + adj[cur][i].second;
			
            //더 짧은 거리를 발견하면 dist[]갱신, 우선순위 큐에 넣음
			if (dist[next] > nextDist) {
				dist[next] = nextDist;
				pq.push({ -nextDist, next });
			}
		}
	}
	return dist;
}
  1. 각 정점은 한 번씩 방문되고,큐의 최대 크기는 O(|E|), 이 경우 우선순위 큐에 원소를 추가하거나 삭제하는 데는 O(|lg|E||)의 시간, 총 O(|E||lg|E||)
  • visited 배열 사용

  1. 정점의 수가 적거나 간선의 수가 매우 많은 경우 빠름
  2. 다음에 방문할 정점을 별도의 큐에 보관하는 대신 매번 반복문을 이용해 방문하지 않은 정점 중 dist[]가 가장 작은 값을 찾음
  3. 방문해야 할 정점들의 목록을 저장하는 큐가 없기 때문에, 각 정점을 방문했는지 여부를 나타내는 별도의 배열 visited[] 유지
  4. O(|V|^2+|E|) 의 시간 복잡도를 가짐
vector<int> dijkstra2(int src) {
	vector<int> dist(V, INF);
    //각 정점을 방문했는지 여부 저장
	vector<bool> visited(V, false);
	dist[src] = 0; visited[src] = false;

	while (true) {
		int closest = INF, cur;
        
        //아직 방문하지 않은 정점 중 가장 가까운 정점을 찾음
		for (int i = 0; i < V; i++) {
			if (dist[i] < closest && !visited[i]) {
				cur = i;
				closest = dist[i];
			}
		}
		if (closest == INF) continue;
		visited[cur] = true;
        
        //가장 가까운 정점을 방문
		for (int i = 0; i < adj[cur].size(); i++) {
			int next = adj[cur][i].first;
			if (visited[next]) continue;
			int nextDist = dist[cur] + adj[cur][i].second;
			dist[next] = min(dist[next], nextDist);
		}
	}
	return dist;
}

이 문제는 다익스트라를 알면 바로 풀 수 있는 문제기 때문에 소스코드를 바로 첨부 (시간 초과 때문에 배열을 사용할 순 없고, 큐를 사용해도 아슬아슬하게 통과된다)

✏️Source Code

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

const int V_MAX = 20001;
const int INF = 1e8;

int V, E, K;
vector<pair<int, int>> adj[V_MAX]; //(vertex, weight)
vector<int> dist;

void input() {
	cin >> V >> E >> K;
	dist = vector<int>(V + 1, INF);

	//input adj data
	for (int i = 0; i < E; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		adj[u].push_back({ v,w });
	}
}

void dijkstra() {
	priority_queue<pair<int, int>> pq; // weight, vertex
	pq.push({ 0, K });
	dist[K] = 0;

	while (!pq.empty()) {
		int cost = -pq.top().first;
		int cur = pq.top().second;
		pq.pop();

		//already found shorter pathway
		if (dist[cur] < cost) continue;
		
		for (int i = 0; i < adj[cur].size(); i++) {
			int next = adj[cur][i].first;
			int nextDist = cost + adj[cur][i].second;

			if (dist[next] > nextDist) {
				dist[next] = nextDist;
				pq.push({ -nextDist, next });
			}
		}
	}

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

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	input();
	dijkstra();
	return 0;
}

profile
Backend 개발자 지망생

0개의 댓글