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

다익스트라 알고리즘

다익스트라 알고리즘은 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 구하는 알고리즘입니다. 단 한개의 음의 가중치라도 허용되지 않으며, 만약 음의 가중치가 있는 그래프라면 다익스트라 알고리즘 대신 벨맨 포드 알고리즘을 사용하는 방법이 있습니다.

 

구현방법

다익스트라 알고리즘을 구현하는 방법에는 반복 문을 사용하는 방법과 우선순위 큐를 사용하는 방법이 존재합니다. 현재 포스팅에서는 이해가 쉬운 반복문을 사용하는 방법을 배운 뒤 이를 응용하여 우선순위 큐로 구현하는 법으로 넘어가겠습니다 :)

 

구현 

길이를 저장할 배열과, 해당 노드에 방문했는지 확인할 배열이 필요합니다. 이 예제에서는 dist, ch 라고 이름을 붙히겠습니다. dist와 ch 배열의 크기는 노드의 개수로 선언합니다.

 

1. 그리고 dist 배열을 매우 큰 값으로 초기화 합니다. 여기서 매우 큰 값은 M이라고 표현하겠습니다.

M

M

M

M

M

M

2. 시작 노드는 0으로 초기화 합니다. 

0

M

M

M

M

M

3. M을 제외한 그리고 방문하지 않은 가장 작은 배열 값을 체크합니다. 여기서는 0번 노드가 되겠네요. 

0 (✓)

M

M

M

M

M

4. 0번 노드에서 갈 수 있는 노드들의 가중치를 더합니다.

                                가중치가 도출 되는 과정 (만약 dist[2]가 dist[0] + 0 보다 크다면 dist[2] = dist[0] + 0 이다.)

즉, 어떠한 값을 거쳐서 가는게 한번에 가는것 보다 빠르다면 거쳐가는 가중치를 더해줍니다.

0 (✓)

2

3

M

M

M

5. 새로운 값이 나온다면, 이중에서 체크가 안된 가장 작은 값을 찾은 뒤 해당 노드에서 갈 수 있는 노드들의 가중치를 또 더합니다.

0 (✓)

2 (✓)

3

7

M

M

6. 더 이상 체크할 요소가 없을 때까지 반복 된 후 종료합니다. 

                                     M은 체크 될 수 없으므로 이렇게 프로그램이 종료되게 됩니다. 

0 (✓)

2 (✓)

3 (✓)

7 (✓)

M

11 (✓)

우리는 반복문을 통해 각 배열에서 체크가 안된 가장 작은 값을 찾습니다. 이는 O(n) 의 시간 복잡도를 갖고 있습니다. 하지만 우선 순위 큐를 사용하므로써 우리는 O(log n) 복잡도 안에 가장 작은 값을 찾을 수 있습니다. 우선 순위 큐는 어떠한 값을 출력할 때 사용자가 정해놓은 출력 순서로 값을 출력하기 때문입니다. 

 

코드

import java.util.*;

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

    public Node(int idx, int weight) {
        this.idx = idx;
        this.weight = weight;
    }
    public int compareTo(Node o){ // 1
        return this.weight - o.weight;
    }
} 

public class Main {
    static ArrayList<ArrayList<Node>> graph;
    static int[] dis;
    static boolean [] ch;
    static int V,E,K;

    public static void Dijkstra() {
        PriorityQueue<Node> pq = new PriorityQueue<>();

        pq.add(new Node(K-1,0));
        while(!pq.isEmpty()){
            Node tmp = pq.poll();
            if(ch[tmp.idx]) continue;
            ch[tmp.idx] = true;
            for(Node o : graph.get(tmp.idx)){
                if(dis[o.idx] > dis[tmp.idx] + o.weight){
                    dis[o.idx] = dis[tmp.idx] + o.weight;
                    pq.add(new Node(o.idx, dis[o.idx]));
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        V = sc.nextInt();
        E = sc.nextInt();
        K = sc.nextInt();
        graph = new ArrayList<ArrayList<Node>>();
        for (int i = 0; i < V; i++) {
            graph.add(new ArrayList<Node>());
        }
        for (int i = 0; i < E; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            graph.get(a-1).add(new Node(b-1, c));
        }
        ch = new boolean[V];

        dis = new int[V];
        Arrays.fill(dis, Integer.MAX_VALUE); // 2
        dis[K-1] = 0;
        Dijkstra();
        for (int i = 0; i < V; i++) {
            if(dis[i] == Integer.MAX_VALUE)
                System.out.println("INF");
            else                 System.out.println(dis[i]);
        }
    }
}