1753 최단경로(C++)

최단경로

다익스트라 알고리즘 기초 문제

1. 문제

---

간단 설명

노드와 간선 개수, 시작 노드와 간선 정보들이 주어질 때,

최단 경로를 출력하는 문제

2. 문제 분석

---

주의점

1. 노드는 1부터 시작한다

2. 2차원 배열로 선언할 경우, 간선 정보를 저장하는 배열의 크기가 메모리를 초과함

필요변수

노드 개수, 간선 개수 int V, E (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000)

시작 노드 int start

간선의 정보를 저장할 int a, b, c

이를 저장할 간선의 연결 리스트 vector< pair<int, int >> map[MAX]

다익스트라 거리 계산을 위한 int dist[MAX]

알고리즘

1. 노드 개수와 간선 개수, 시작 노드 입력받기
2. 간선 정보를 연결리스트에 입력받기
3. 다익스트라 시작
    3-1. dist 배열 INF로 초기화
    3-2. 우선순위 큐 선언 후 {0, start} (코스트, 시작노드)를 넣음
    3-3. 시작 노드의 dist를 0으로 초기화
    3-4. 우선순위 큐가 빌때까지 반복
        3-4-1. cost 는 우선순위 큐의 가장 앞에 있는 최소 코스트
        3-4-2. cur는 가장 앞에 있는 노드 번호를 저장한다
        3-4-3. 우선순위 큐의 가장 앞을 pop 
        3-4-4. 이 노드와 연결된 모든 노드의 정보를 확인한다
            3-4-4-1. 현재 노드와 연결된 다음 노드의 번호를 next에 저장
            3-4-4-2. 현재 노드와 연결된 다음 노드의 코스트를 nCost에 저장
            3-4-4-3. `현재 노드까지의 거리와 다음 노드까지의 코스트의 합을` `다익스트라 배열에 저장`된 값과 비교
                - 더 작다면 이를 갱신한다

4. 이후 다익스트라 배열 d에 저장된 값을 출력 후 종료한다

3. 소스코드

---

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

using namespace std;

#define MAX 20001
#define INF 21e8

int V, E, start;
int dist[MAX]; 
vector<pair<int, int>>map[MAX];


void dijkstra(int start) {
	for (int i = 1; i <= V; i++)
		dist[i] = INF;

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

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

		for (int i = 0; i < map[cur].size(); i++) {
			int next = map[cur][i].first;
			int nCost = map[cur][i].second;

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

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	// freopen_s(new FILE*, "input.txt", "r", stdin);

	cin >> V >> E >> start;
	for (int i = 0; i < E; i++) {
		int a, b, c; cin >> a >> b >> c;
		map[a].push_back({ b, c });
	}

	
	dijkstra(start);

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

}

• 2024-01-18 개선버전. 우선순위 큐를 오름차순 우선순위로 변경

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

using namespace std;

#define MAX 20001
#define INF 21e8 // 2100000000 21억

int V, E, start_node;
vector<pair<int, int>> map[MAX];
int dist[MAX];

void dijkstra(int start) {
	// 1. dist 배열 초기화
	for (int i = 1; i <= V; i++) {
		dist[i] = 21e8;
	}

	// 2. pq 선언 및 초기세팅
	// 우선순위큐를 pair형의 오름차순으로 정렬하도록 선언
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
	pq.push({ 0, start }); 
	dist[start] = 0; // 시작노드의 거리는 0으로 저장

	while (!pq.empty()) {
		int curDist = pq.top().first; // 이전 버전과 다르게 음수화 시킬 필요 없음
		int cur = pq.top().second;
		pq.pop(); // 꼭 pop을 해줄것
		
		// cur 노드와 연결된 노드들을 검색
		for (int i = 0; i < map[cur].size(); i++) {
			int nextDist = map[cur][i].first; 
			int next = map[cur][i].second;

			if (curDist + nextDist < dist[next]) {
				dist[next] = curDist + nextDist;
				pq.push({ dist[next], next }); // 음수화 할 필요 없이 그냥 저장
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	// freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> V >> E >> start_node;

	for (int i = 0; i < E; i++) {
		int start, end, cost;
		cin >> start >> end >> cost;
		//우선순위큐 정렬을 위해  코스트, 도착 노드 순으로 넣어줌
		map[start].push_back({ cost, end }); 
	}

	dijkstra(start_node);

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

	return 0;
}