Today I Learned

오늘은 다익스트라 알고리즘에 대해 정리해보려한다.

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

이미지 출처 : 80000coding

최단 경로 문제. 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘

특징

• 가능한 적은 비용으로 가장 빠르게 답에 가는 경로를 찾아내야하는 문제에서 매우 자주 쓰인다.

• 그래프의 방향 유무는 상관없으나 간선들의 가중치가 하나라도 음수면 적용할 수 없다.

• 한 정점에서 모든 정점까지의 최단경로를 정확하게 찾는 데 특화되어있다.

• 그래프의 정점과 간선이 많을 경우 오래걸릴 수 있다.

• 각 단계에서 최소 가중치를 가진 정점을 선택하는 탐욕적(greedy) 방식을 사용한다.

• 추가로 각 과정을 memoization하는 동적계획법(DP) 방식도 있다.

• 전반적으로 큐를 이용한 BFS를 큐 대신 우선순위큐를 사용하는 방식으로 구현되었다고 생각하면 된다.

• 시간복잡도 : V가 정점의 수, E가 간선의 수일 때, 처음 고안되었을 때는 배열과 선형탐색을 사용해 O(V^2)였다. 하지만, 우선순위큐를 사용해 개선된 다익스트라 알고리즘은 O((V+E)log V)로 성능이 좋아졌다.

구현 과정

아래의 단계를 차례대로 수행하면서, 우선순위 큐를 사용하여 현재까지 가장 작은 거리를 가진 정점을 선택하고 거리를 업데이트한다.

1. 그래프와 정점 초기화 : 최단 경로를 찾을 그래프를 인접 행렬(혹은 리스트)로 표현하고 정점 개수를 파악한 뒤 출발 정점을 선택한다.

2. 거리 배열 생성 : 출발정점으로부터 각 정점까지 최단거리를 저장할 배열을 만든다. index 0번 즉, 출발정점 자신은 거리가 0이고, 나머지 정점들은 무한대로 값을 초기화 한다.
   (자바를 사용할 경우 Integer.MAX_VALUE;로 가능한 최대값을 넣는다.)

3. 우선순위 큐 준비 : 최소 거리를 가진 정점을 빠르게 선택하기위해 우선순위큐(최소 힙)을 생성하고 출발 정점을 우선순위큐에 넣는다.

4. 알고리즘 실행

   4-1. 우선순위 큐에서 가장 작은 거리를 가진 정점을 꺼낸다.
   4-2. 해당 정점과 연결된 모든 인접 정점을 순회하면서 거리 배열과 비교해 현재 경로가 더 짧으면 거리배열에서 해당 정점의 거리를 갱신하고 우선순위 큐에 넣는다.
   4-3. 최단 거리가 계산되면 각 정점까지의 최단 거리 값을 출력한다.

구현 코드

우선순위큐를 사용한 개선된 방식이다.

import java.io.*;
import java.util.*;
public class A_DijkstraPQ {
    static List<List<Node>> graph;
    static int V;
    static int[] distance;

    // 노드 클래스 생성. PQ를 활용한 비교를 위해 Comparable 구현
    static class Node implements Comparable<Node> {
        int vertex;
        int weight;

        // 생성자
        Node(int vertex, int weight) {
            this.vertex = vertex;
            this.weight = weight;
        }

        // Comparable의 비교 메서드를 가중치 기준으로 오버라이드
        @Override
        public int compareTo(Node other) {
            return Integer.compare(this.weight, other.weight);
        }
    }

    public static void dijkstra(int index) {
        // 기본 pq라서 최소힙(최소값 반환)
        Queue<Node> pq = new PriorityQueue<>();
        // 최단 거리를 저장할 배열
        distance = new int[V];
        // 배열을 최대값으로 초기화
        Arrays.fill(distance, Integer.MAX_VALUE);
        // 출발노드는 거리가 0
        distance[index] = 0;
        pq.offer(new Node(index, 0));

        while(!pq.isEmpty()){
            Node node = pq.poll();
            int nv = node.vertex;
            int nw = node.weight;

            // 꺼낸 노드의 가중치가 최단 거리 배열에 비해 크면 패스
            if(nw > distance[nv]) continue;

            // 인접한 정점을 돌면서 최단거리 배열에 비해 작으면 갱신
            for(Node linkedNode : graph.get(nv)) {
                int lv = linkedNode.vertex;
                int lw = linkedNode.weight;
                if(nw+lw < distance[lv]){
                    distance[lv] = nw+lW;
                    pq.offer(new Node(lv, distance[lv]))
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        V = Integer.parseInt(st.nextToken()); // 정점의 개수
        int E = Integer.parseInt(st.nextToken()); // 간선의 개수
        graph = new ArrayList<>();
        // 인접리스트로 그래프 생성
        for(int i=0; i<V; i++){
            graph.add(new ArrayList<>());
        }
        // 
        for(int j=0; j<E; j++){
            st = new StringTokenizer(br.readLine());

            int start = Integer.parseInt(st.nextToken()); // 시작노드
            int end = Integer.parseInt(st.nextToken()); // 도착노드
            int w = Integer.parseInt(st.nextToken()); // 가중치(거리)

            graph.get(start).add(new Node(end, w));
            // 양방향일 경우
            graph.get(end).add(new Node(start, w));
        }

        // 알고리즘 실행
        dijkstra(0);
        // 결과 출력
        for(int i=0; i<V; i++){
        	System.out.println(i+ "번 정점까지의 최단 거리는 " + distance[i]);
    	}
}

참고 사이트 : myeongju00