반응형
그래프에서 한점에서 한점까지 최단거리를 계산하는데 사용되는 다익스트라 알고리즘의 핵심 코드 입니다.
void dijkstra(int start)
{
//시작 지점 넣고
d[start] = 0;
priority_queue<node, vector<node>, compare> pq;
pq.push(node(start, 0));
//포문 돌린다.
while (!pq.empty()) {
//현재 위치 거리 꺼내고
int current = pq.top().next;
int distance = pq.top().distance;
pq.pop();
//최단거리가 아닌경우 스킵
if(d[current] < distance) continue;
//현재에서 이어져있는 모든 노드 호출
for (int i = 0; i < arr[current].size(); i++) {
//선택된 노드의 인접노드
int next = arr[current][i].first;
//선택된 노드를 인접 노드로 거쳐서 가는 비용
int nextDistance = distance + arr[current][i].second;
//기존의 최소비용보다 더 저렴하다면 교체합니다.
if(nextDistance < d[next])
{
d[next] = nextDistance;
pq.push(node(next, nextDistance));
}
}
}
}
노드 들은 pair를 사용해도 되고 node 구조체를 만들어도 좋음
struct node{
int next;
int distance;
node(int a, int b)
{
next = a;
distance = b;
}
};
vector<pair<int, int>> arr[MAX];
노드들이 큐에 쌓일때 짧은 거리순으로 쌓일 수 있게 만들어준 컴페어 함수
struct compare
{
bool operator()(node &i, node &j)
{
return i.distance > j.distance;
}
};
하 이정도만 알고 바로바로 쓸 수 있어도 다익스트라를 응용해서 푸는 문제는 어느정도 다룰 수 있을 겁니다.
하지만 제일 중요한건 이 코드들을 까먹지 않게 계속 사용하는 것..... 사실 공부하고 이해하는것 보다 이게 더 어렵죠
반응형
'Programming > Algorithm(알고리즘)' 카테고리의 다른 글
최소신장트리 (MST) 핵심 코드 | c++ (0) | 2021.02.19 |
---|---|
자료구조-펜윅트리 핵심 코드 | c++ (0) | 2021.01.29 |
시간복잡도와 공간복잡도 개념. 알고리즘 초보라면 필독!! (0) | 2020.05.05 |