다익스트라 알고리즘 구현방법 (Java)

4. 구현

(1) 순차 탐색

저번 게시글에서 설명한 작동원리 그대로 구현한 방식이다.
방문한 정점과 그렇지 않은 정점 구분을 위해서, 방문배열을 사용한다.
현재 정점에서 갈 수 있는 간선을 통해 dist[] 배열을 최신화하고, 방문 배열을 통해, 현재까지 방문하지 않은 정점 중 시작 정점에서 최단 거리로 갈 수 있는 정점을 택해야 한다.
여기서 최악의 경우, 정점의 수가 N개라면, 매번 N번의 정점을 탐색해 다음 방문해야할 정점을 찾아야 하고, 이 행위를 모든 정점을 방문할 때까지 반복해야 하므로 최악의 시간복잡도는 O(N^2)이 든다.

import java.io.*;
import java.util.*;

public class 순차탐색_다익스트라 {
    static int [] dist = new int [N];     // N이 변수가 아니라 상수라 치자 
    static boolean [] visited = new boolean [N];
    static ArrayList<Node> [] lists;

     public static void main(String[] args) throws IOException {
         // 배열의 원소가 시작노드, 배열 안의 나열된 값들은 <도착노드, 가중치> 묶음
         lists = new ArrayList [N+1]; 

         for(int i = 1; i < N+1; i++){
             lists[i] = new ArrayList<>();
         }

         // 값 입력 받아서 인접 리스트 채우기 
         // ...
         Dijkstra(1);
    }

    public int 최단거리노드찾기() {
        int min_dist = Integer.MAX_VALUE;
        int min_idx = -1;

        for(int i = 0; i < N; i++){
            if(visited[i]) continue; 
            if(dist[i] < min_dist){
                min_dist = dist[i];
                min_idx = i;
            }
        }
        return min_idx;
    }

    // 시작노드를 인수로 받아서, 해당 노드로부터 모든 노드의 최단 거리를 dist에 입력
    public void Dijkstra(int start) {
        // 1. dist 배열 초기화 
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;
        visited[start] = true;
        // 2. 본 다익스트라 시작 -> 모든 노드 방문할 때까지만 반복하면 됨. 
        for(int i = 0; i < N-1; i++){
            int now_node = 최단거리노드찾기();
            visited[now_node] = true;

            for(int j = 0; j < lists[now_node].size(); i++){
                // 만약 현재까지 j로 가는 최단거리보다 now_node를 거쳐서 j로 가는 최단거리가 더 짧을 경우 갱신
                if(dist[j] > dist[now_node] + lists[now_node].get(j).w){
                    dist[j] = dist[now_node] + lists[now_node].get(j).w;
                }
            }
        }
    }

}

class Node {
    int v; // 도착 노드
    int w; // 도착 노드까지 가는 간선의 가중치 

    public Node(int v, int w) {
        this.v = v;
        this.w = w;
    }   
}

(2) 우선순위 큐 활용

★ 구현 방법 ★ 

/*
    0. 인접 리스트, 최단 거리 배열 최신화 

    1. 정점 객체의 시작노드로부터의 거리가 짧은 순으로 정렬되는 우선순위 큐 생성
    1-1 해당 우선순위 큐에 시작 정점을 넣고 '우선순위 큐'가 빌 때까지 반복문 시작

    2. Node curNode = queue.poll() 하여 현재 방문하려는 정점 꺼내기
    2-1. if(dist[curNode.idx] < curNode.cost) continue; 를 통해 유효성 확인
    2-2. 현재 방문 중인 정점이 유효하다면 이를 이용해 최단 거리 배열 갱신
    2-3. 갱신된 정점만 다시 queue에 넣기. 
*/

a. 우선순위 큐의 역할

우선순위 큐는 방문배열 대용역할이다.
한 번 최단 거리 배열(dist)을 갱신할 때마다 다음 방문할 노드를 O(N^2)의 시간 복잡도로 방문해야 했던 것에 비해 시작노드로 부터 최단 거리인 Node 순으로 정렬한 우선순위 큐를 쓴다면, 그저 queue.poll()한 값을 꺼내 쓰면 되므로 시간 복잡도면에서 크게 효율이 상승한다. (얼마나 상승했는지는 후술하겠다.)

b. Node 객체 속 cost의 2가지 의미

일단 Node라는 클래스를 정의하겠다.

class Node {
    int idx; // 정점 번호
    int cost; // 인접리스트에서는 간선의 가중치, 다익스트라 내부에서는 현재 갱신된 dist 값
}

위와 같이 2가지 의미로 구분되어 쓰인다.

1. 인접리스트 구현 시 해당 Node 속 cost란 멤버변수는 간선의 가중치로 쓰임.
2. 다익스트라 내부에서 사용되는 Node 객체의 cost는 갱신된 dist 값을 가르킴.

1번은 당연하니까 넘어가자. 2번은 무슨 의미인가? 먼저 우선순위큐 활용한 다익스트라의 예시를 보여주겠다.

    // 시작노드를 인수로 받아서, 해당 노드로부터 모든 노드의 최단 거리를 dist에 입력
    public void Dijkstra(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>((o1,o2) -> o1.fast_cost - o2.fast_cost);
        pq.add(new Node(start, 0));

        while(!pq.isEmpty()){
            Node now = pq.poll();
            if(now.cost > dist[now.idx]) continue;
            for(int i = 0; i < list[now.idx].size(); i++){
                int dest_idx = list[now.idx].get(i).idx;
                int compare_dist = list[now.idx].get(i).weight + dist[now.idx];

                if(compare_dist < dist[dest_idx]){
                    dist[dest_idx] = compare_dist;
                    pq.add(new Node(dest_idx, compare_dist));
                }
            }
        }
    }

여기서 맨 마지막 if문을 보면, 현재 확인 중인 정점을 활용한 거리 비용이 기존 비용보다 작으면 갱신하는 모습을 볼 수 있다. 또한 새로운 Node 객체를 만들어 다시 queue에 삽입한다. 위와 같이 다익스트라 내부 우선순위큐의 정렬기준에 맞춰 다음 정점을 찾기 위해 여기서의 Node.cost는 현재 갱신된 최단 거리 비용을 뜻한다.

c. if(dist[curNode.idx] < curNode.cost) continue 하는 이유?

하지만 위와 같이 최단 거리를 cost로 가진 객체를 우선순위 큐에 넣는다고 해서, 방문 배열 활용 다익스트라보다 속도면에서 효율적이라 볼 수 없다. 왜냐하면 queue.poll()한 객체 A의 cost > dist[A.idx]의 cost 일 경우 즉, 현재 방문하려는 정점이 주장하는 dist 값보다 dist 배열의 갱신된 값이 더 작다면,
이미 해당 정점은 이전 poll()한 객체에 의해 더 단거리 최단비용으로 갱신되었다는 소리이다. 이미 더 작은 값으로 갱신되었는데, 현재 정점 비용으로 다시 계산하는 것은 무의미하다. 따라서 해당 경우는 넘어가도록 조치를 취해준다.

d. 시간복잡도는? 🤔💭

우선순위 큐 활용 다익스트라는 우선순위 큐 활용 부분만 뺀다면 1단 반복문과 조건문으로만 이루어져 있기 때문에, 우선순위 큐 활용이 시간이 제일 많이 든다. 따라서 우선순위 큐 활용부분만 생각해주면 된다. N개의 값을 우선순위큐에 삽입한다면 O(logN)의 시간이 든다. 추출 시에도 마찬가지로 O(logN)의 시간이 든다.
정점의 수를 V, 간선의 수를 E라 할 때, 삽입은 얼마나 이루어질까? 우선순위 큐 삽입은 최단 거리 배열이 갱신될 때만 이루어진다. 최악의 경우, 현재 방문한 정점에서 갈 수 있는 정점을 고려할 때마다 갱신될 것이므로 간선의 수만큼 삽입 될 것이다. 따라서 O(ElogE)의 시간 복잡도가 필요하다. 밀집 그래프까지 가정한다면 E <= V^2 개까지 가능하므로 O(ElogV^2), O(2*ElogV) 즉 O(ElogV)로도 표현이 가능하다.
추출은 당연히 Queue가 빌때까지 계속 되어야 한다. Queue에는 최소 정점의 개수, 최대로 많아도 간선의 최대값인 정점의 개수의 제곱을 넘지 않을 것이다. 따라서 시간복잡도는 O(VlogV)이다. 둘을 합치면 최종적으로

O((V+E)logV)의 시간복잡도를 필요로 한다.

a. 예시

1.

2.

3.

4.

5.

이제 다음이 중요한데, 이미 방문한 정점4가 우선순위 큐의 front에 와있다. 하지만 잘보면 정점4까지의 최단거리라 저장해놓은 것이 5로 이미 최신화된 최단 거리 배열 속 dist[4]의 값보다 크다. 그래서 queue.poll() 하자마자 버린다.

6.

7.

이후 남은 정점 속 dist 값도 최신화된 dist 배열(최단 거리 배열) 속 dist[6]보다 값이 크므로 그냥 PASS 한다.

b. 구현

import java.io.*;
import java.util.*;

public class 순차탐색_다익스트라 {
    static int N = 9;
    static int [] dist = new int [N];
    static ArrayList<Vertex> [] lists;

     public static void main(String[] args) throws IOException {
         // 0. initialize
         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

         lists = new ArrayList [N+1]; 
         Arrays.fill(dist, Integer.MAX_VALUE);
         for(int i = 1; i < N+1; i++){
             lists[i] = new ArrayList<>();
         }

         int edge_cnt = Integer.parseInt(br.readLin());
         for(int i = 0; i < edge_cnt; i++){
             StringTokenizer st = new StringTokenizer(br.readLine());
             int start     = Integer.parseInt(st.nextToken());
             int end     = Integer.parseInt(st.nextToken());
             int cost = Integer.parseInt(st.nextToken());
             lists[start].add(new Vertex(end, cost));
         }

         // 1부터 모든 정점까지의 최단거리를 찾겠다.
         Dijkstra(1);
    }


    // 시작노드를 인수로 받아서, 해당 노드로부터 모든 노드의 최단 거리를 dist에 입력
    public void Dijkstra(int start) {
        PriorityQueue<Vertex> pq = new PriorityQueue<>((o1,o2) -> o1.fast_cost - o2.fast_cost);
        pq.add(new Vertex(start, 0));

        while(!pq.isEmpty()){
            Vertex now = pq.poll();
            if(now.cost > dist[now.idx]) continue;
            for(int i = 0; i < list[now.idx].size(); i++){
                int dest_idx = list[now.idx].get(i).idx;
                int compare_dist = list[now.idx].get(i).weight + dist[now.idx];

                if(compare_dist < dist[dest_idx]){
                    dist[dest_idx] = compare_dist;
                    pq.add(new Vertex(dest_idx, compare_dist));
                }
            }
        }
    }

}

class Vertex {
    int idx;        // 현 정점의 번호
    int cost;     // 시작 정점에서 현 정점까지의 최단 거리 (큐에 집어넣을 당시의 최단거리라서 최신화된 dist 배열과 차이가 날 수 있음)
    public Vertex (int idx, int fast_cost){
        this.idx = idx;
        this.fast_cost = fast_cost;
    }
}