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

개요

다익스트라 알고리즘은 최단경로를 찾기 위한 알고리즘이다.

주의할 점은 음수 가중치를 갖는 간선을 가지면 안된다.
음수가 되는 사이클을 돌면 가중치가 음의 무한까지 발산하기 때문

음수 간선의 중요성

설명

최단 경로는?

인접 노드라고 해서 최단경로가 아니라는 점에 주목하자.

위와 같은 형태의 그래프에서 0->3 까지 바로 갈 수 있지만,
0->1->2->3 경로로 가는 거리가 가장 짧기 때문에 최단경로는 후자가 된다.

 

다익스트라 알고리즘은 경로를 기준으로 하는 우선순위 큐를 이용한다.
우선순위 큐에는 정점의 번호와 지금까지 찾은 해당 정점까지의 최단거리를 쌍으로 갖는다.

 

최단거리 쌍(시작점으로 부터거리, 정점의 번호)

 

각 정점까지 최단거리를 저장하는 배열 dist[]를 정의한다.
해당 정점으로 부터 갈 수 있는 모든 노드를 검사한다.

 

최단거리를 저장하는 배열 dist[] 를 정의했지만, 이는 계속해서 수정될 수 있다.
정확한 dist[]의 정의는 탐색하면서 찾은 해당 노드까지의 최단 거리라고 생각하면 될 것 같다.

 

다른 루트를 통해서 5번째 노드 dist[5](기존값 10) 보다 더 짧은 경로(더 짧은 경로 7)를 발견했다고 치자, 이 경우에 dist[5]를 갱신해준다.

여기서 문제가 발생하는데, 5번째 노드로 가는 요소가 2개({5, 10}, {5, 7})가 존재하게 된다.

 

여기서 dist[5] 값을 갱신 한 뒤 dist[5] 보다 큰 값을 가지는 5번째 노드로 가는 첫번째 요소는 처리하지 않는 방식을 이용한다.

나머지 방식은 너비우선탐색과 동일하다.

구현

코드

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Vector;

public class 다익스트라 {
    // 매우 큰 값
    final static int INF = 987654321;
    // 정점의 개수
    static int V;
    // 그래프의 인접 리스트
    static Vector<Vector<Pair>> adj;

    static class Pair {
        int cost, here;

        public Pair(int cost, int here) {
            this.cost = cost;
            this.here = here;
        }
    }

    static Vector<Integer> dijkstra(int src) {
        // 최단 경로 저장 배열
        // 매우 큰 값으로 초기화
        Vector<Integer> dist = new Vector<>();
        for (int i = 0; i < V; i++) {
            dist.add(INF);
        }

        // 현재 위치 값 0으로 바꾸기
        dist.set(src, 0);

        // 우선순위 큐 생성
        // 최단 경로 우선순위
        PriorityQueue<Pair> pq = new PriorityQueue<>(new Comparator<Pair>() {

            @Override
            public int compare(Pair o1, Pair o2) {
                return o1.cost - o2.cost;
            }

        });

        pq.add(new Pair(0, src));

        while (!pq.isEmpty()) {
            int cost = pq.peek().cost;
            int here = pq.peek().here;
            pq.poll();
            // 지금 꺼냇 것보다 더 짧은 경로를 알고 있다면 무시할 것
            if (dist.get(here) < cost)
                continue;

            // 인접한 정점들을 모두 검사할 것
            for (int i = 0; i < adj.get(here).size(); i++) {
                int there = adj.get(here).get(i).here;
                int nextDist = cost + adj.get(here).get(i).cost;
                // 더 짧은 경로를 발견하면 dist[] 를 갱신, 우선순위 큐로 넣는다.
                if (dist.get(there) > nextDist) {
                    dist.set(there, nextDist);
                    pq.add(new Pair(nextDist, there));
                }
            }
        }
        return dist;
    }

    public static void main(String[] args) {
        // 정점의 개수
        V = 4;

        // 인접리스트를 벡터로 초기화 해준다.
        adj = new Vector<>();

        // 인접리스트 각 노드를 추가해준다.
        for (int i = 0; i < V; ++i) {
            adj.add(new Vector<>());
        }

        // 그래프 데이터 삽입

        adj.get(0).add(new Pair(2, 1));
        adj.get(1).add(new Pair(2, 0));

        adj.get(1).add(new Pair(4, 2));
        adj.get(2).add(new Pair(4, 1));

        adj.get(2).add(new Pair(3, 3));
        adj.get(3).add(new Pair(3, 2));

        adj.get(3).add(new Pair(12, 0));
        adj.get(0).add(new Pair(12, 3));

        Vector<Integer> resultDest = dijkstra(0);

        for (int i = 0; i < resultDest.size(); i++) {
            System.out.println("노드 0 에서 " + i + "까지 최단거리 : " + resultDest.get(i));
        }

    }
}

 

결과

노드 0 에서 0까지 최단거리 : 0
노드 0 에서 1까지 최단거리 : 2
노드 0 에서 2까지 최단거리 : 6
노드 0 에서 3까지 최단거리 : 9