[그래프] 다익스트라 알고리즘

다익스트라

 - '최단 경로는 여러 개의 최단경로로 이루어졌다.'

 - 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘, 하나의 정점(Node)에서부터 다른 정점까지로 가는 최단 경로를 알 수 있습니다. (대신, 가중치가 음수인 경우 적용할 수 없습니다.)

 - 기본적으로 하나의 최단 경로를 구할 때, 이전까지 구한 최단 경로 정보를 그대로 활용한다는 특징이 있습니다.

 

다익스트라의 작동과정

1. 출발노드 선정

2. 출발노드를 기준으로 연결된 노드마다 최소 비용 저장

3. 방문하지 않은 노드 중 최소 비용의 노드 선택

4. 다른 노드로 이동할 경우, 최소 비용을 갱신하며 이동

5. 3~4번 반복

 

www.acmicpc.net/problem/1753

1753번: 최단경로

 

Comparable을 활용한 객체 정렬

static class Node implements Comparable<Node> {
    int num, weight;

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

    @Override
    public int compareTo(Node node) {
        return this.weight - node.weight;
    }
}

 Comparator Interface인 Comparable을 사용자 정의 Class에 implements 후, compareTo 메서드를 오버라이딩을 통해 재정의합니다. 이는 그래프 탐색의 인자가 되고 우선순위 큐에 저장되는 객체들의 정렬 기준이 됩니다.

 

다익스트라 알고리즘

public static void findMinRoute(int start) {
    PriorityQueue<Node> pq = new PriorityQueue<>();
    pq.offer(new Node(start, 0));
    boolean[] visited = new boolean[V+1];  
    
    int[] minRoute = new int[V+1]
    Arrays.fill(minRoute, MAX);
    minRoute[start] = 0;

    while(!pq.isEmpty()) {
        Node n = pq.poll();
        start = n.num;

        if(visited[start]) continue;
        visited[start] = true;

        for(Node node: graph[start]) {
            int end = node.num;

            if(minRoute[end] > minRoute[start] + node.weight && !visited[end]) {
                minRoute[end] = minRoute[start] + node.weight;
                pq.offer(new Node(end, minRoute[end]));
            }
        }
    }
}

 위에서 언급한 작동과정을 코드로 나타낸 것입니다. Node Class에 compareTo 메서드가 오버라이딩됐으므로 우선순위 큐인 pq의 객체 정렬 기준이 정해졌습니다. (가중치인 weigth를 기준으로 오름차순 정렬)

 그래서 이미 방문한 노드의 경우, 최소 비용을 구했기 때문에 다시 방문할 필요가 없습니다.