[개념 정리] 다익스트라 Dijkstra

다익스트라란?

최단 경로 탐색 중 하나로 시작점을 기준으로 모든 정점에 대해 최단 경로를 찾음

단! 가중치는 음수이면 안된다! -> 왜?? 참고

 

인접 행렬로 표현된 그래프의 경우 시간 복잡도 O(n^2) -> 낮은 가중치 탐색해야함
우선순위 큐 사용하여 시간 복잡도 O(mlog n)까지 낮출 수 있음 → 개선된 다익스트라 알고리즘

기본 코드(우선순위 큐 사용, 다익스트라 메서드만 작성)

static void dijkstra(int start) {
        dp[start] = 0;
        PriorityQueue<Node> pq = new PriorityQueue<Node>();
        pq.offer(new Node(start, 0));
        
        while (!pq.isEmpty()) {
            int cur = pq.peek().idx;
            int dist = pq.peek().dist;
            pq.poll();
            
            if (dp[cur] < dist) continue;
            for (Node next : list[cur]) {
                int nextDist = dist + next.dist;
                
                if (dp[next.idx] > nextDist) {
                    dp[next.idx] = nextDist;
                    pq.offer(new Node(next.idx, nextDist));
                }
            }
        }
    }

 

백준에서 관련 문제 풀어보기!

https://www.acmicpc.net/problemset?sort=ac_desc&algo=22

https://www.acmicpc.net/problem/10282