다익스트라 알고리즘이란?

다익스트라 알고리즘이란?

출발지 노드로부터 가장 거리가 가까운 노드들을 순차적으로 추가하면, 모든 노드들로 최단 거리를 구할 수 있다.

매순간 가장 가까운 노드들을 추가하는 것이 최단 거리를 구할 수 있는 이유는?

최단 거리보다 더 가까운 거리가 있다면, 그 거리가 최단 거리로 뽑혔을 것이기 때문이다. 모순이 발생한다.

가장 가까운 노드들을 추가하고 해야할 일은?

가장 가까운 노드를 추가하고, 해당 노드를 통해서 갈 수 있는 경로들을 갱신해줘야 한다. 추가된 경로도 반영해야 하기 때문이다.

코드 구현은 어떻게 할까?

우선순위큐를 이용한 방식과 배열을 이용한 방식이 있다.

우선순위큐를 이용한 방식은 어떻게?

출발지 노드를 제외한 나머지 노드들의 회수만큼 돌리는 반복문과 내부에는 우선순위큐에 비용을 넣도록 하면 된다. O(VlogV)가 발생할 것이다.

O(logV)에 대해서 자세히 설명해줄래?

우선순위큐에 만약에 N개의 원소가 들어있다면, 삽입시에 O(logN)의 시간복잡도가 필요하다. k번째 가까운 노드를 찾을 때 최대 V^2만큼의 개수가 원소가 있을 수 있다. 하지만 로그의 성질에 의해 O(logV^2) = O(2logV) = O(logV)가 된다.

우선순위큐 코드

    static void dijkstra(int start, int[] dist, int[][] cost, int N){
        for(int i = 1; i <= N; i++){
            dist[i] = Integer.MAX_VALUE;
        }
        dist[start] = 0;
        
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (a[1] - b[1]));
        pq.add(new int[]{start, 0});
        
        while(!pq.isEmpty()){
            int node = pq.peek()[0];
            int distance = pq.peek()[1];
            pq.poll();
            
            if(dist[node] < distance) continue;
            
            for(int i = 1; i <= N; i++){
                if(cost[node][i] != 0){
                    if(dist[node] + cost[node][i] < dist[i]){
                        dist[i] = dist[node] + cost[node][i];
                        pq.add(new int[]{i, dist[i]});
                    }
                }
            }
        }
    }

배열을 이용한 코드 구현은?

배열을 이용한 코드 구현은, 우선순위큐에서 가장 거리 값을 뽑는 것을 배열로 직접 구현하면 된다.

배열 코드

class Main
{
    int getMin(int start, int[] dist){
        int result = Integer.MAX_VALUE;
        int idx = 0;
        
        for(int i = 0; i < dist.length; i++){
            if(result > dist[i]){
                result = dist[i];
                idx = i;
            }
        }    
        
        return idx;
    }
    
    public void dijkstra(int[][] cost, int start){
        int N = cost.length;
        int[] dist = new int[cost.length];
        for(int i = 0; i < dist.length; i++){
            dist[i] = Integer.MAX_VALUE;
        }
        dist[start] = 0;
        
        for(int i = 0; i < N; i++){
            int ret = getMin(start, dist); // O(N) 
            
            for(int next = 0; next < N; next++){
                if(cost[ret][next] != 0 && dist[ret] + cost[ret][next] < dist[next]){
                    dist[next] = dist[ret] + cost[ret][next];
                }
            }
        }
    }
}

Colored