[Algorithm] 다익스트라(dijkstra) 알고리즘

다익스트라 알고리즘

다익스트라 알고리즘은, 모든 간선의 weight가 0이상 일 때 사용가능한 알고리즘으로, 특정 vertex를 출발점으로 하여 모든 vertex까지의 최소 거리를 구하는 알고리즘입니다. 

 

알고리즘의 동작 원리는, "매 단계마다, 도달할 수 있는 정점 중에서 시작점으로부터 거리가 가장 가까운 정점을 확정해 나가는 방식입니다.

 

weight가 작은 노드부터 계속 가지고와야 하다보니, 다익스트라 알고리즘은 일반적으로 PriorityQueue를 사용하여 구현합니다. 최솟값을 가진 노드를 찾기 위해 일반 배열의 경우 복잡도가 O(n)이지만, PriorityQueue의 경우에는 O(log n)입니다.

 

구현 - 노드 정의

package baek1753;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

class Node implements Comparable<Node> {
    int end, weight;

    public Node(int end, int weight) {
        this.end = end;
        this.weight = weight;
    }

    @Override
    public int compareTo(Node node) {
        return Integer.compare(weight, node.weight);
    }
}

weight를 가진 간선의 도착 지점에 end 정점 인덱스가 저장됩니다.

 

구현 - 다익스트라 함수 정의

    private static void dikstra(int start) {
        PriorityQueue<Node> queue = new PriorityQueue<>();
        // PriorityQueue를 사용하는 이유
        // offer(입력): O(logN)
        // peek(get) : O(1)
        // poll(반환): O(logN)
        // size :       O(1)
        // PriorityQueue 종류
        // 최소힙을 사용하는 priorityqueue: new PriorityQueue<>()
        // 최대힙을 사용하는 priorityqueue: new PriorityQeue<>(Collections.reverseOrder())

        // 다익스트라 알고리즘의 흐름
        // 현재 위치에서 최소 거리로 가는 애를 확정한다.
        // 현재 위치에서 나머지 애들도 거리를 비교해서 업데이트한다.
        // 그다음 최소 거리로 가는 애로를 현재 위치로 변경한다...
        // 이런 흐름 -> fifo이되, 거리가 작은 애가 우선순위가 높아야 한다.
        boolean[] check = new boolean[v + 1]; // check 배열 생성
        queue.add(new Node(start, 0)); // start 노드 생성 및 enqueue 
        dist[start] = 0; // start 정점까지의 거리 = 0

        while (!queue.isEmpty()) { // queue가 빌 때까지
            Node curNode = queue.poll(); // queue에서 가장 weight가 가장 작은 애를 꺼내라
            int cur = curNode.end; // 현재 노드의 도착 정점

            if(check[cur]==true) continue; // 만약 check되어있다면 이미 최소 거리임이 확정된 정점이다. -> pass
            check[cur] = true; // 그렇지 않다면 이번에 현재 노드의 도착 정점의 최소 거리를 확정짓는다.

            for (Node node : list[cur]) { // 확정된 현재 노드에서 갈 수 있는 다음 노드들에 대하여
                if (dist[node.end] > dist[cur] + node.weight) {
                    dist[node.end] = dist[cur]+ node.weight; // 다음 노드까지의 거리가 현재 기록되어 있는 거리보다 짧다면
                    queue.add(new Node(node.end, dist[node.end])); // enque해라. 이때 weight는 시작 정점 ~ 해당 정점까지의 거리이다.
                }
            }
        }
    }

`check`배열이 없어도 다익스트라 알고리즘이 정상적으로 동작하긴 합니다. 하지만, 시간 개선을 위해 일반적으로 check 배열을 추가해서 사용합니다.

 

하단에는 백준 1753번 문제에 대한 전체 코드가 있습니다. 일반적인 다익스트라 알고리즘 문제에 대한 풀이 코드입니다.

package baek1753;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

class Node implements Comparable<Node> {
    int end, weight;

    public Node(int end, int weight) {
        this.end = end;
        this.weight = weight;
    }

    @Override
    public int compareTo(Node node) {
        return Integer.compare(weight, node.weight);
    }
}

public class Main {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    private static final int INF = 100_000_000;
    static int v,e,k;
    static List<Node>[] list;
    static int[] dist;

    public static void main(String[] args) throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        v = Integer.parseInt(st.nextToken());
        e = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(br.readLine());
        list = new ArrayList[v + 1]; // list[i] = i번째 vertex와 연결되어 있는 edge의 도착 vertaex정보와 edge의 weight

        dist = new int[v + 1]; // 특정 vertex로부터 각 노드까지의 도착점

        Arrays.fill(dist, INF);
        for (int i = 1; i < v + 1; i++) {
            list[i] = new ArrayList<>();
        }
        for (int i = 1; i < e+1; i++) {
            st = new StringTokenizer(br.readLine());
            int start=Integer.parseInt(st.nextToken());
            int end=Integer.parseInt(st.nextToken());
            int weight=Integer.parseInt(st.nextToken());
            list[start].add(new Node(end, weight));

        }
        StringBuilder sb = new StringBuilder();
        dikstra(k);
        for (int i = 1; i <= v; i++) {
            if(dist[i]==INF) sb.append("INF\n");
            else sb.append(dist[i] + "\n");
        }
        bw.write(sb.toString());
        bw.close();
        br.close();
    }

    private static void dikstra(int start) {
        PriorityQueue<Node> queue = new PriorityQueue<>();
        // PriorityQueue를 사용하는 이유
        // offer(입력): O(logN)
        // peek(get) : O(1)
        // poll(반환): O(logN)
        // size :       O(1)
        // PriorityQueue 종류
        // 최소힙을 사용하는 priorityqueue: new PriorityQueue<>()
        // 최대힙을 사용하는 priorityqueue: new PriorityQeue<>(Collections.reverseOrder())

        // 다익스트라 알고리즘의 흐름
        // 현재 위치에서 최소 거리로 가는 애를 확정한다.
        // 현재 위치에서 나머지 애들도 거리를 비교해서 업데이트한다.
        // 그다음 최소 거리로 가는 애로를 현재 위치로 변경한다...
        // 이런 흐름 -> fifo이되, 거리가 작은 애가 우선순위가 높아야 한다.
        boolean[] check = new boolean[v + 1];
        queue.add(new Node(start, 0));
        dist[start] = 0;

        while (!queue.isEmpty()) {
            Node curNode = queue.poll();
            int cur = curNode.end;

            if(check[cur]==true) continue;
            check[cur] = true;

            for (Node node : list[cur]) {
                if (dist[node.end] > dist[cur] + node.weight) {
                    dist[node.end] = dist[cur]+ node.weight;
                    queue.add(new Node(node.end, dist[node.end]));
                }
            }
        }
    }
}