[Java] 다익스트라 알고리즘 - 최단경로

그래프 문제에서 대표적인 최단 경로를 구하는 알고리즘입니다. 인공위성 GPS 소프트웨어 등에서 가장 많이 사용된다고 알려져 있습니다. 하나의 정점에서 모든 정점으로 가는 최단 경로를 알려줍니다. (단, 음의 간선을 포함할 수 없음)

응용이 많은 부분이라 기본적인 내용을 확실히 숙지하여야 합니다.

 

동작과정

1. 출발 노드를 설정
2. 출발노드 기준으로 각 노드의 최소비용을 저장
3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택
4. 해당 노드를 거쳐서 톡정한 노드로 가는 경우를 고려하여 최소 비용을 갱신
5. 위 과정에서 3~4 과정을 반복

시간복잡도

• 힙의 구조를 활용하면 : O(N * log N)

참고 사이트

• 동빈나 : https://blog.naver.com/ndb796/221234424646
• 위키백과 : https://ko.wikipedia.org/wiki/%EB%8D%B0%EC%9D%B4%ED%81%AC%EC%8A%A4%ED%8A%B8%EB%9D%BC_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

데이크스트라 알고리즘 - 위키백과, 우리 모두의 백과사전

 

기본코드

아래와 같은 그래프가 존재한다고 합시다. 0에서 시작하여 각 노드까지의 최단 거리를 구하는 코드입니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.PriorityQueue;

class Node implements Comparable<Node>{
    int n;
    int dist;

    Node(int a, int b) {
        n = a;
        dist = b;
    }

    @Override
    public int compareTo(Node tar) {
        if (tar.dist < this.dist) return 1; 
        if (tar.dist > this.dist) return -1; 
        return 0;
    }    

}

class 다익스크라_기본코드_단방향 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static ArrayList<ArrayList<Node>> alist = new ArrayList<ArrayList<Node>>();
    static PriorityQueue<Node> q = new PriorityQueue<Node>();

    static int[] best;
    static int[] used;

    public static void main(String[] args) throws IOException {        

        int n = 5;
        best = new int[n];
        used = new int[n];

        for (int i = 0; i<n; i++) {
            alist.add(new ArrayList<>());
        }

        alist.get(0).add(new Node(2, 70));
        alist.get(0).add(new Node(1, 10));
        alist.get(0).add(new Node(4, 170));        
        alist.get(1).add(new Node(2, 50));
        alist.get(1).add(new Node(3, 20));
        alist.get(2).add(new Node(4, 60));    
        alist.get(3).add(new Node(2, 15));

        //다익스트라 초기세팅
        q.add(new Node(0, 0));
        for (int i = 0; i<n; i++) best[i] = Integer.MAX_VALUE;
        best[0] = 0;

        while(!q.isEmpty()) {
            Node via = q.poll();
            if (used[via.n] == 1) continue; //이미 했었던 경유지면 탈락
            if (best[via.n] != via.dist) continue; //예전정보면 탈락

            used[via.n] = 1;             

            for (int i = 0; i<alist.get(via.n).size(); i++) {
                Node tar = alist.get(via.n).get(i);

                //지금까지 구했던 최고의 비용보다, 더 저렴한 비용이 발견되면 
                if (best[tar.n] > via.dist + tar.dist) {
                    best[tar.n] = via.dist + tar.dist; //갱신 
                    q.add(new Node(tar.n, best[tar.n]));
                }
            }
        }

        System.out.println(best[4]);

        br.close();
        bw.close();
    }
}

0에서 시작하여 각 노드들의 최단 거리는 아래와 같이 빨강색 경로로 이동을하여 4까지 가는 최단경로의 거리는 105 입니다.