[Algo] 다익스트라 알고리즘

그래프 알고리즘을 해결하기 위한 대표적인 알고리즘으로는

1. 다익스트라 알고리즘
2. 벨만-포드 알고리즘
3. 플로이드 - 우셜 알고리즘

위 세가지의 알고리즘이 대표적입니다. 그 중에서 이번에는 다익스트라 알고리즘을 정리해보았습니다.

다익스트라 알고리즘(Dijkstra Algorithm)은 음이 아닌 가중 그래프에서의 단일 쌍, 단일 출발, 단일 도착 최단 경로 문제를 해결하기 위한 알고리즘이며, V개의 정점과 음수가 아닌 E개의 간성을 가진 그래프 G에서 특정 출발 정점(S)에서 부터 다른 모든 정점까지의 최단경로를 구하는 알고리즘 입니다.

즉, 다익스트라 알고리즘을 사용하기에 가장 적합한 문제는 최단 경로 문제를 해결하는데 가장 효과적인 알고리즘입니다.

다익스트라 알고리즘의 특징으로는

• 각 정점을 최대 한번씩만 방문하여 최단 거리를 확보합니다. (단, 음의 가중치를 가질 수 없습니다.)
• 아직 방문하지 않은 정점들 중 최단거리인 점을 찾아 방문하여 최단거리를 확정하고, 이를 반복하는 방식으로 진행됩니다.
• 총 V * V번 연산이 필요하여 O(V^2)의 시간복잡도를 가집니다.
• 방문하지 않은 정점 중에서 최단 거리가 최소인 정점을 찾는 과정에서 우선순위 큐 (= 힙 자료구조)를 이용하면 더욱 개선된 알고리즘이 가능합니다.

최악의 경우 모든 간선을 확인할 때마다 거리 배열이 갱신이 된다고 하면, 최소 힙에는 최대 E번 정점을 넣게 됩니다. (간선의 개수는 E개 이므로)
최소 힙에 E개의 정점이 있을 때, 하나의 정점을 꺼낼 때 마다 logE의 연산이 필요합니다. (최소 힙 삭제연산의 시간복잡도)
우선순위 큐를 사용하는 경우 ElogE = ElogV^2 = 2ElogV (간선 -> 정점 - > 큐)로 O(ElogV)의 시간복잡도로 개선할 수 있습니다.

BOJ 1753번 최단 경로 문제

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

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

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

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

public class Main {
    private static final int INF = Integer.MAX_VALUE;
    static int V,E,K;
    static List<Node>[] list;
    static boolean[] visit;
    static int[] dist;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(br.readLine());
        list = new ArrayList[V+1];
        dist = new int[V+1];
        visit = new boolean[V+1];

        Arrays.fill(dist,INF);

        for(int i=1;i<=V;i++){
            list[i] = new ArrayList<>();
        }

        for(int i=0;i<E;i++){
            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            list[a].add(new Node(b,c));
        }
        
        dijkstra(K);
        
        for(int i=1;i<=V;i++){
            if(dist[i] == INF) sb.append("INF\n");
            else {
                sb.append(dist[i]).append("\n");
            }
        }
        System.out.println(sb);

    }
    static void dijkstra(int K) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(K,0));
        dist[K] = 0;

        while(!pq.isEmpty()){
            Node Ncur = pq.poll();
            int cur = Ncur.end;

            if(visit[cur]) continue;
            visit[cur] = true;

            for(Node node : list[cur]){
                if(dist[node.end] > dist[cur] + node.weight){
                    dist[node.end] = dist[cur] + node.weight;
                    pq.offer(new Node(node.end,dist[node.end]));
                }
            }
        }
    }

}