다익스트라 (Dijkstra)

📌 다익스트라 알고리즘 (Dijkstra)

특정 노드에서 다른 모든 노드로 향하는 최대or최소 거리를 구하는 알고리즘 (음의 간선은 사용 불가능)
(Greedy & DP)

❗ 동작

1. 제공된 거리 정보로 인접 리스트 or 인접 행렬 생성
2. 다른 모든 노드로 향하는 최대 or 최소 경로를 저장하는 dp를 하나 선언
   (dp 전체를 MAX_VALUE로 초기화, 시작 노드는 cost = 0으로 설정)
3. 우선순위큐를 사용해서 가장 거리가 짧은 것 먼저 탐색
   1. 값을 꺼냈는데, 이미 더 작은 값으로 갱신 되어 있는 경우
      ⇒ 값을 새로 갱신할 필요 없음 (continue)
   2. 꺼낸 노드에 연결되어 있는 노드들을 순차적으로 탐색
      ⇒ 새로 update한 거리가 dp에 저장된 거리보다 큰 경우, update X & 우선순위 큐에 새로 저장 X

 

⏰ 시간 복잡도

우선순위 큐 사용 : O(ElogV)

간선의 갯수를 E개, 노드의 갯수를 V개 라고 하자. 다익스트라 알고리즘은 E개의 간선을 우선순위 큐에 넣었다가 빼는 연산이다. 모든 간선이 한번씩 검사된다는 점에서 O(E)번 반복한다. 그리고 각 간선마다 우선순위 큐에서 add&poll 연산이 일어나는데, 그래프에 중복 간선이 없다면 E는 V^2 이하이다. 왜냐하면 모든 노드가 연결된 경우 간선의 갯수는 V(V-1)개 이기 때문이다. 따라서 하나의 간선에서 우선순위 큐에 add&poll하는 연산은 최악의 경우 O(logV) 이므로, 전체 간선 E개에서 우선순위 큐 연산을 하면 "O(ElogV)"가 소요된다.

 

🗣️ 코드

백준 1504, 1753

(만약 공간 복잡도가 넉넉하지 않다면 인접 리스트를 활용하여 그래프를 초기화한다.)

// 최단 경로 찾기
private static int[] dijkstra(int start){
    // 2. 거리의 최솟값을 저장하는 DP 선언
    int cost[] = new int[n+1];
    Arrays.fill(cost, MAX_VALUE);
    cost[start] = 0;

    // 3. 우선순위큐를 사용해서 cost가 가장 적은 것을 먼저 탐색
    PriorityQueue<Pair> queue = new PriorityQueue<>((p1, p2) -> (p1.cost - p2.cost));
    queue.add(new Pair(0, start));

    while(!queue.isEmpty()){
        Pair p = queue.poll();
        
        // 3-1. 이미 더 작은 값으로 갱신되어 있는 경우 (더 확인하지 않고 다음으로 넘어감)
        if(p.cost > cost[p.node]){
            continue;
        }
        for(int i=1; i<=n; i++){
            if(arr[p.node][i] != 0){
                // 3-2. 업데이트 할지 말지 결정
                if(arr[p.node][i] + p.cost < cost[i]){
                    cost[i] = arr[p.node][i] + p.cost;
                    queue.add(new Pair(cost[i], i));
                }
            }
        }
    }
    return cost;
}