그래프-다익스트라 code | c++

그래프에서 한점에서 한점까지 최단거리를 계산하는데 사용되는 다익스트라 알고리즘의 핵심 코드 입니다.

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;
    }
};

 

하 이정도만 알고 바로바로 쓸 수 있어도 다익스트라를 응용해서 푸는 문제는 어느정도 다룰 수 있을 겁니다.

하지만 제일 중요한건 이 코드들을 까먹지 않게 계속 사용하는 것..... 사실 공부하고 이해하는것 보다 이게 더 어렵죠