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

목차

다익스트라 알고리즘이란?

다익스트라(Dijkstra) 알고리즘은 DP를 활용한 대표적인 최단 경로(Shortest Path) 탐색 알고리즘이다. 다익스트라 알고리즘은 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 구하는 알고리즘이다. 

 

다익스트라 알고리즘은 DP와 그리디 문제로도 분류되기도 한다. DP 문제로 분류되는 이유는 최단 거리는 여러 개의 최단 거리로 이루어져 있기 때문이다. A에서 D로 가는 최단 경로를 예로 들어보겠다. A에서 B로 가고 B에서 C로 가고 C에서 D로 가는 게 A에서 D로 가는 최단 경로라면 그 과정 속에 있던 A에서 B로 가는 경로도 최단 경로이고, B에서 C로 가는 경로도 최단 경로이고 C에서 D로 가는 경로 또한 최단 경로여야 하기 때문이다. 그리고 다익스트라가 그리디 문제로도 분류되는 이유는 바로 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택하기 때문이다.

 

우선 간단한 예시를 한번 보겠다. 이 예시에서는 1부터 다른 모든 노드로 가는 최단 경로를 구한다고 가정해보겠다.

 

예시 1

 

우선 기본적으로 노드 1에 붙어있는 간선을 통해 갈 수 있는 노드들을 보겠다. 즉, 1에 당장 붙어있는 노드인 2, 3, 4까지의 최단 경로를 각각 3, 6, 7이라고 할 수 있다. 이렇게 하면 다음과 같이 표시할 수 있다.

 

 

다음으로는, 현재 갈 수 있는 위치 중에서 가장 짧은 위치인 노드 2를 기준으로 확인을 해보겠다.

 

이때, 기존에 경로 1 -> 3의 비용이 6이었는데 노드 2를 거쳐서 가면 (1 -> 2 -> 3) 총비용이 4로 더 낮다는 것을 확인할 수 있게 된다. 이때 비용을 새로 갱신하는 것이다. 즉, 현재까지 알고 있던 3으로 가는 최소 비용 6을 새롭게 4로 갱신한다. 여기서 알 수 있듯이 다익스트라 알고리즘은 현재까지 알고 있던 최단 경로를 계속해서 갱신한다.

 

조금 더 구체적인 다익스트라 알고리즘의 과정은 다음과 같다.

 

알고리즘 과정 : 

 

 1. 출발 노드를 설정한다.

 

 2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장한다.

 

 3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다.

 

 4. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신한다.

 

 5. 위 과정에서 3번 ~ 4번을 반복한다.

 

이제 조금 더 복잡한 예제를 한번 보겠다.

 

예시 2

 

우선 이 그래프에 표시되어 있는 상태를 2차원 배열로 옮겨보면 다음과 같다. 이 2차원 배열은 특정 행에서 열로 가능 비용을 표시했다. 여기서 INF는 무한, 즉 다이렉트로 연결되어 있지 않은 상태를 뜻한다.

 

 

1번 노드에서 다른 노드로 가는 최소 비용을 구한다고 가정해보겠다.

 

 

1번 노드는 2, 3, 4번 노드와 연결이 되어 있다. 현재 당장 자신과 연결되어 있는 노드의 비용으로 갱신을 해준다. 이렇게 하면 다음과 같은 1차원 배열을 만들 수 있다. 현재 노드 5와 6은 노드 1과 연결이 안 되어있어서 INF로 설정해준다.

 

 

이제 이 상태에서 현재 방문하지 않은 노드 중에서 가장 비용이 적은 4번 노드를 선택한다. 즉, 다음에 4번 노드를 확인해준다. 따라서, 4번 노드를 거쳐서 가는 경우를 모두 고려해서 최소 비용 배열을 갱신해주면 된다.

 

 

4번 노드 같은 경우는 2번, 3번, 그리고 5번 노드와 연결이 되어 있는 것을 확인할 수 있다. 1번 노드에서 4번 노드로 갈 때는 1의 비용이 든다. 즉, 이 상태에서 3번 노드로 갈 때는 3의 비용이 드는데 1번 노드에서 4번 노드로 갈 때 1의 비용이 들어서 총 4의 비용이 드는 것을 확인할 수 있다. 하지만 기존에 1번 노드에서 바로 3번 노드로 갈 때는 5의 비용이 들었다. 즉, 4번 노드를 거쳐서 가는 게 비용이 더 적으므로 새롭게 4로 비용을 갱신해준다. 이렇게 특정한 노드를 거쳐서 가는 경우 비용이 더 싸다면 그 더 싼 비용으로 배열을 갱신해준다. 나머지도 마찬가지로 갱신하면 다음과 같다.

 

 

이제 다음으로 방문하지 않은 노드 중에서 가장 비용이 적은 노드는 2번 노드이다. 

 

 

확인을 해 보면 2를 거쳐서 가더라도 최소 비용이 갱신되지 않는다. 따라서 배열을 그대로 유지한다.

 

 

다음으로 방문하지 않은 노드 중에서 가장 비용이 적은 노드는 5번 노드이다.

 

 

5를 거쳐서 3으로 가는 비용을 한번 확인해보겠다. 5로 갈 때 드는 비용은 1에서 4로 가고 4에서 5로 가서 총 2이다. 그리고 5에서 3으로 갈 때 비용이 1이므로 총비용은 3이다. 5를 거쳐서 3으로 가는 경우 비용이 3이므로 기존의 4보다 더 저렴하다. 따라서 비용을 3으로 갱신해준다. 

추가로, 이전에는 6으로 가는 경로가 없어서 비용이 무한, 즉 INF로 설정되어 있었다. 하지만, 5를 거쳐서 6으로 가는 경우 비용이 4로 기존의 무한보다 더 저렴하다. 마찬가지로 6으로 가는 비용을 4로 다음과 같이 갱신해준다.

 

 

이후에 방문하지 않은 노드 중에서 가장 저렴한 노드인 3번 노드를 방문해서 마찬가지로 확인해준다.

 

 

이때 최소 비용 갱신은 이루어지지 않는다.

 

 

그리고 마지막으로 6번 노드도 마찬가지로 확인해준다.

 

 

6번 노드를 방문한 후에도 최소 비용 갱신은 이루어지지 않는다. 따라서 1번 노드에서 출발했을 때의 최소 비용 배열은 최종적으로 다음과 같다.

 

 

 

코드 1

 

import java.io.*;
import java.util.*;
public class Main {
   static int number = 6;  //노드의 개수
   static int INF = 1000000000;  //무한
   static int[][] a = { //전체 그래프 초기화
       {0, 2, 5, 1, INF, INF},
       {2, 0, 3, 2, INF, INF},
       {5, 3, 0, 3, 1, 5},
       {1, 2, 3, 0, 1, INF},
       {INF, INF, 1, 1, 0, 2},
       {INF, INF, 5, INF, 2, 0}
   };
   static boolean[] v; //방문한 노드들
   static int[] d;  //거리

   public static void main(String[] args) throws IOException {
       v = new boolean[number]; //방문한 노드
       d = new int[number]; //거리
       dijkstra(0);
       for (int i = 0; i < number; i++) {
           System.out.print(d[i] + " ");
       }
   }

   // 가장 최소 거리를 가지는 정점 반환
   static int getSmallIndex() {
       int min = INF;
       int index = 0;
       for (int i = 0; i < number; i++) {
           if (d[i] < min && !v[i]) {
               min = d[i];
               index = i;
           }
       }
       return index;
   }

   // 다익스트라 함수
   static void dijkstra(int start) {
       for (int i = 0; i < number; i++) {
           d[i] = a[start][i];
       }
       v[start] = true;
       for (int i = 0; i < number - 2; i++) {
           int current = getSmallIndex();
           v[current] = true;
           for (int j = 0; j < number; j++) {
               if (!v[j]) {
                   if (d[current] + a[current][j] < d[j]) {
                       d[j] = d[current] + a[current][j];
                   }
               }
           }
       }
   }
}

 

이 알고리즘은 구현하기는 비교적 쉬워도 O(n^2)의 시간 복잡도를 가지고 있다는 것이다. 따라서 최대한 빠르게 작동시켜야 하는 경우 힙 구조 (우선순위 큐)를 활용해서 구현하면 O(n logn)의 시간 복잡도를 가지게 할 수 있다. 

 

코드 2

 

import java.io.*;
import java.util.*;
public class Main {
    static int V, E, K;
    static int[] dist;
    static ArrayList[] adjacentList;

    static class Node implements Comparable<Node> { //노드 클래스
        int index, cost;

        Node(int index, int cost) {
            this.index = index;
            this.cost = cost;
        }

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(br.readLine());  //시작 노드

        //우선 거리 배열 무한대로 초기화
        dist = new int[V+1];
        for (int i = 1; i <= V; i++) {
            dist[i] = Integer.MAX_VALUE;
        }
        
        //인접리스트 (그래프) 초기화
        adjacentList = new ArrayList[V+1];
        for (int i = 1; i <= V; i++) {
            adjacentList[i] = new ArrayList<Node>();
        }

        //방향간선 인접리스트 입력
        for (int i = 1; i <= E; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            adjacentList[u].add(new Node(v, w));
        }

        //다익스트라 함수 실행
        dijkstra(K);

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= V; i++) {
            if (dist[i] == Integer.MAX_VALUE) {
                sb.append("INF\n");
            } else {
                sb.append(dist[i] + "\n");
            }
        }
        System.out.print(sb);
    }

    static void dijkstra(int K) {
        //출발지 비용은 0으로 하고 출발지를 pq에 넣고 시작
        PriorityQueue<Node> pq = new PriorityQueue<>();
        dist[K] = 0;
        pq.add(new Node(K, 0));

        while (!pq.isEmpty()) {
            Node current = pq.poll();

            //더 큰 가중치로 도착한 경우 패스
            if (current.cost > dist[current.index]) continue;

            //현재 위치에 연결된 간선 탐색
            int length = adjacentList[current.index].size();
            for (int i = 0; i < length; i++) {
                Node next = (Node) adjacentList[current.index].get(i);

                //cost가 더 작으면 갱신
                if (dist[next.index] > current.cost + next.cost) {
                    dist[next.index] = current.cost + next.cost;
                    pq.add(new Node(next.index, dist[next.index]));
                }
            }
        }
    }
}

 

이 알고리즘은 우선순위 큐를 이용해서 구현한 것이다. 시간 복잡도도 O(E logV)로 더 저렴하다.