알고리즘
[알고리즘]- 다익스트라 C++기본 코드 구조
doyyy_0
2024. 10. 14. 14:33
1. 다익스트라란 ?
음수 사이클이 없는 그래프에서 한 정점에서 모든 정점까지의 최단거리를 구하는 방법입니다.
각 단계에서 가장 짧은 경로를 선택하며 진행하기 때문에 그리디의 성질을 가지고 있습니다. 힙으로 그리디 성질을 이용합니다.
각 노드 사이에 가중치가 있고 방향이 있든 없든 상관이 없습니다.
기본 코드 구조는 다음과 같습니다.
#include <iostream>
#include <vector>
#include <queue>
#include <functional> // for std::greater
#include <climits> // for INT_MAX
using namespace std;
const int INF = INT_MAX; // 무한대를 나타내는 상수 (최댓값)
vector<vector<pair<int, int>>> graph; // 인접 리스트 (정점, 가중치)
// 다익스트라 알고리즘 함수
void dijkstra(int start, int N) {
// 최단 거리 저장용 배열 (초기에는 모두 무한대)
vector<int> dist(N + 1, INF);
dist[start] = 0; // 시작점의 거리는 0으로 설정
// 우선순위 큐 (최소 힙, 거리 기준 오름차순 정렬)
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, start}); // (거리, 정점) 삽입
while (!pq.empty()) {
int cur_dist = pq.top().first;
int cur = pq.top().second;
pq.pop();
// 이미 더 짧은 경로가 있다면 스킵
if (dist[cur] < cur_dist) continue;
// 인접한 모든 정점에 대해 거리 갱신
for (auto& edge : graph[cur]) {
int next = edge.first;
int weight = edge.second;
int next_dist = cur_dist + weight;
// 더 짧은 경로를 찾았다면 갱신하고 우선순위 큐에 삽입
if (dist[next] > next_dist) {
dist[next] = next_dist;
pq.push({next_dist, next});
}
}
}
// 결과 출력
for (int i = 1; i <= N; ++i) {
if (dist[i] == INF)
cout << "INF "; // 경로가 없는 경우
else
cout << dist[i] << " "; // 최단 거리 출력
}
cout << endl;
}
int main() {
int N, M; // N: 정점 수, M: 간선 수
cin >> N >> M;
graph.resize(N + 1); // 그래프 크기 조정 (1-indexed)
// 간선 입력
for (int i = 0; i < M; ++i) {
int u, v, w;
cin >> u >> v >> w;
graph[u].push_back({v, w}); // u -> v의 가중치 w
graph[v].push_back({u, w}); // 무방향 그래프일 경우
}
int start;
cin >> start; // 시작 정점 입력
// 다익스트라 알고리즘 실행
dijkstra(start, N);
return 0;
}
이 코드를 꼼꼼히 이해하고 반복적 학습을 통해 외울 정도로 훈련해야합니다.