[알고리즘] 다익스트라 알고리즘(Dijkstra Algorithm) 기초

다익스트라(Dijkstra)?

그래프에서 한 정점에서 다른 정점까지의 최단 경로를 구하는 알고리즘이다.

그리디(Greedy) 알고리즘으로 최소신장트리(MST)의 프림 알고리즘과 유사하다.

• 프림은 시작 정점이 정해져 있지 않고, 어떠한 간선들을 선택해서 최소 비용을 만드는 것에 초점을 둔다.
• 다익스트라는 시작 정점이 정해져 있고, 도착 정점으로 가는 최소 비용에 초점을 둔다.

최단 경로? 

간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로이다.

다익스트라 알고리즘 특징

1. 시작 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다.
   • 하나의 시작 정점이 반드시 필요하다.
   • 음의 가중치를 허용하지 않는다.
   • 최단 경로의 부분 경로도 최단임이 보장된다.
2. 시작 정점에서 비용이 최소인 정점을 선택해 나가면서 최단 경로를 구하는 방식이다.
   • 그리디(Greedy) 알고리즘의 특징이다.
   • 모든 정점을 탐색하기 때문에 큰 그래프에서는 비효율적이다.

동작 과정

초기화

1. 시작 정점을 입력 받는다.
2. 비용을 저장할 Cost 배열을 ∞로 초기화한 후, 시작 정점은 비용을 0으로 설정한다.
3. 방문 여부를 기록하는 배열 또는 우선순위 큐를 준비한다.

탐색 반복

1. 방문하지 않은 정점 중 현재까지 비용이 가장 적은 정점을 선택한다.
2. 선택된 정점이 가지고 있는 비용과 선택된 정점과 인접한 정점까지의 비용의 합이 기존 비용보다 적다면 비용을 갱신한다.
3. 더 이상 방문한 정점이 없거나, 모든 정점의 최단 경로가 확정되면 반복을 종료한다.

구현 방법 1 : 선형 탐색

‘방문하지 않은 정점 중 현재까지 비용이 가장 적은 정점’을 찾는 방식이 선형 탐색인 것이다.

비용 배열(Cost[])을 앞에서부터 순차적으로 탐색하여 정점을 찾아내야 하기 때문에, 정점의 개수만큼 탐색을 수행한다.

⏱️시간 복잡도 : $O(N^{2}+E)$

• 정점의 개수가 N개일 때, 현재까지 비용이 가장 적은 정점을 찾는데 $O(N^2)$
  • 모든 정점에 대해 크기N의 비용 배열을 선형 탐색하며 최소값을 찾기 때문에,$O(N^2)$의 시간이 필요하다.
• 간선의 개수가 E개일 때, 각 노드마다 인접한 정점의 최소 비용을 갱신할 때 $O(E)$
  • 각 노드마다 인접한 정점을 확인하는 건 모든 간선을 확인하는 것과 같기 때문에 $O(E)$의 시간이 필요하다.

---

아래의 코드는 백준에 있는 다익스트라 기본 문제를 선형 탐색 방법으로 풀어본 예시 코드이다. (1916번 : 최소 비용 구하기)

public class 최소비용구하기 {
    static int N, M, cost[]; // cost : 최소 비용을 저장할 배열
    static boolean[] visit; // 방문 여부를 기록하는 배열
    static ArrayList<ArrayList<int[]>> list = new ArrayList<>();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine())+1;
        M = Integer.parseInt(br.readLine());
        cost = new int[N]; visit = new boolean[N];
        for(int i=0; i<N; i++){cost[i]=Integer.MAX_VALUE;} // 최대 값으로 배열 초기화
        for(int i=0; i<N; i++){list.add(new ArrayList<>());}
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            list.get(u).add(new int[]{v,c});
        }
        st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken()); // 출발 정점
        int end = Integer.parseInt(st.nextToken()); // 도착 정점
        Dijkstra(start);
        System.out.println(cost[end]); // 도착 정점의 최소 비용을 출력 
    }

    public static void Dijkstra(int s){
        cost[s] = 0; // 시작 정점의 비용을 0으로 설정

        while(true){
            // 방문하지 않은 정점 중 현재까지 비용이 가장 적은 정점을 선택
            int next = -1; // 선택한 정점
            int d = Integer.MAX_VALUE; // 선택한 정점의 현재 비용(A)
            for(int i=1; i<N; i++){
                if(!visit[i] && cost[i]<d){next=i; d=cost[i];}
            }

            if(next==-1) break; // 더이상 방문할 정점이 없으면 탈출
            visit[next] = true; // 선택한 정점 방문 처리

            // 선택된 정점을 기준으로 인접한 정점들의 경로를 갱신
            for(int[] i : list.get(next)){
                // i[0] : 인접한 정점, i[1] : 인접한 정점까지의 비용(간선의 가중치)
                // (선택된 정점의 비용 + 인접한 정점까지의 비용)이 인접한 정점의 현재 비용보다 적으면 갱신
                if(cost[next]+i[1]<cost[i[0]]){
                    cost[i[0]] = cost[next]+i[1];
                }
            }
        }
    }
}

---

구현 방법 2 : 우선순위 큐

선형 탐색을 사용하면 간단히 구현할 수 있지만, $O(N^2+E)$의 시간복잡도로 큰 그래프에서는 비효율적이다. 이를 개선하기 위해 우선순위 큐를 활용한다.

‘현재까지 비용이 가장 적은 정점’을 찾는 방식이 우선순위 큐인 것이다. 선형 탐색과 달리, 우선순위 큐를 사용하면 방문 여부를 저장할 배열이 없어도 된다.

우선순위 큐에서 정렬은 ‘비용이 가장 적은 정점’을 앞으로 오도록 기준을 정한다. 우선순위 큐에 {정점, 비용} 형태로 넣고, 큐에서 꺼낸 정점의 비용이 기존 비용보다 크면 무시한다.

⏱️ 시간 복잡도 : $O(ElogE+ElogE)$

• 각 정점마다 인접한 정점의 최소 비용을 넣을 때 $O(ElogE)$
  • 각 정점마다 인접한 정점 확인하는 것은 모든 간선을 확인하는 것과 같기에 $O(E)$의 시간이 필요하다.
  • 최소 비용이 갱신되어 큐에 원소를 새로 넣을 경우, 큐의 길이는 최대 E가 되고 $O(logE)$의 시간이 필요하다.
• 크기가 E인 우선순위 큐에서 최소 비용을 찾을 때 $O(ElogE)$
  • 모든 정점에 대해 $O(E)$
  • 크기가 E인 우선순위 큐에서 값을 추출한다. $O(logE)$

---

아래의 코드는 백준에 있는 다익스트라 기본 문제를 우선순위 큐 방법으로 풀어본 예시 코드이다. (1916번 : 최소 비용 구하기)

public class 최소비용구하기 {
    static int N, M, cost[]; // cost : 최소 비용을 저장할 배열
    static ArrayList<ArrayList<int[]>> list = new ArrayList<>();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine())+1;
        M = Integer.parseInt(br.readLine()); cost = new int[N];
        for(int i=0; i<N; i++){cost[i]=Integer.MAX_VALUE;} // 최대 값으로 배열 초기화
        for(int i=0; i<N; i++){list.add(new ArrayList<>());}
        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            list.get(u).add(new int[]{v,c});
        }
        st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken()); // 출발 정점
        int end = Integer.parseInt(st.nextToken()); // 도착 정점
        Dijkstra(start);
        System.out.println(cost[end]); // 도착 정점의 최소 비용을 출력
    }

    public static void Dijkstra(int s){
        // {정점, 비용}의 int배열의 형태로 큐에 넣기
        // 비용을 기준으로 오름차순으로 정렬
        PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->(a[1]-b[1]));
        cost[s] = 0; // 시작 정점의 비용을 0으로 설정
        q.add(new int[]{s, 0}); // 시작 노드 큐에 넣기

        while(!q.isEmpty()){
            int[] current = q.poll();
            int curNode = current[0];
            int curCost = current[1];

            // 기존에 저장된 비용보다 큰 경우 무시
            if(curCost>cost[curNode]) continue;

            for(int[] i : list.get(curNode)){
                int nextNode = i[0];
                int nextCost = curCost + i[1]; // 선택된 정점의 비용 + 인접한 정점까지의 비용
                // (선택된 정점의 비용 + 인접한 정점까지의 비용)이 인접한 정점의 현재 비용보다 적으면 갱신
                if(nextCost < cost[nextNode]){
                    cost[nextNode] = nextCost;
                    q.add(new int[]{nextNode, nextCost}); // 다음 정점과 갱신된 비용을 큐에 넣는다
                }
            }
        }
    }
}

추가적으로 알아두면 좋은 내용 

다익스트라 응용 - 역방향 그래프