Algorithm/Graph

[Algorithm] Dijkstra 알고리즘 with JAVA

jundyu 2025. 5. 12. 11:05

데이크스트라 알고리즘

 

들어가며

벌써 3번째 그래프 탐색 알고리즘에 관한 글을 쓰게 되었습니다. 이번 글 역시 아래의 링크를 통해 그래프 이론을 먼저 숙지하고 읽는 겻을 추천드립니다.

 

[Algorithm] 그래프 이론 및 그래프 탐색

들어가며그래프는 제가 가장 좋아하는 알고리즘 분류입니다! 그래프 이론을 배우고 나면 단순한 자료 구조를 넘어서, 너비 우선 탐색, 깊이 우선 탐색, 최단 경로 탐색, 교착상태 판별 등 다양한

jundyu.tistory.com

 

 

Dijkstra : 데이크스트라

1. 알고리즘 명칭

Dijkstra라는 알고리즘의 명칭은 "Edsger Dijkstra"라는 네덜란드의 컴퓨터 과학자의 이름에서 유래되었습니다. 네덜란드식 발음으로는 데이크스트라가 맞지만 한국에선 흔히 다익스트라로도 많이 알려져있습니다. 따라서 이번 글에서도 알고리즘은 계속 데이크스트라로 부르겠습니다.

 

2. 목적

데이크스트라 알고리즘은 특정 정점에서 출발해서 각 정점으로 이동할 때 최소 비용을 구하는 알고리즘입니다. 모든 출발과 도착 정점의 쌍에 대해 최소 비용을 구하는 플로이드 워셜 알고리즘과는 많이 다릅니다.

 

플로이드 워셜 알고리즘은 아래의 글을 참고해주세요.

 

[Algorithm] 그래프 이론 및 그래프 탐색

들어가며그래프는 제가 가장 좋아하는 알고리즘 분류입니다! 그래프 이론을 배우고 나면 단순한 자료 구조를 넘어서, 너비 우선 탐색, 깊이 우선 탐색, 최단 경로 탐색, 교착상태 판별 등 다양한

jundyu.tistory.com

 

3. 특징

1. 간선의 가중치에 음수가 존재하면 안 됨

데이크스트라 알고리즘을 사용하려면 모든 간선의 가중치에 음수가 존재하면 안 됩니다. 우선 데이크스트라 알고리즘에 대한 충분한 설명 후에 그 이유를 다루겠습니다.

 

2. PriorityQueue 자료구조를 사용하여 노드를 관리함

데이크스트라 알고리즘은 그리디 알고리즘입니다. 즉, 지금 당장 가장 좋은 선택을 하면 결국 전체적으로도 최선이 된다는 성질이 있습니다. 왜냐하면 최단 경로의 부분 경로는 항상 최단 경로이기 때문입니다. 따라서 우선순위 큐 자료구조를 이용해서 출발 지점으로부터 비용이 가장 작은 정점의 최소 비용을 갱신해 모든 정점에 대해 확장하는 방식을 가집니다.

 

3. 각 노드에 도달하는 데 필요한 비용을 저장할 배열 필요

그래프를 탐색하기 전 비용 배열은 전부 INFINITY 값으로 채워둡니다. 그리고 그래프 탐색이 완전히 끝난 후 비용이 여전히 INFINITY 값인 노드는 도달할 수 없는 노드이고, 도달할 수 있는 노드는 최소 비용으로 저장됩니다.

 

4. 시간 복잡도는 O((V + E) log V)

 

 

그림으로 보는 데이크스트라 과정

이제 위의 그림과 같이 일반적인 그래프를 예시로 들겠습니다. 방향 그래프이자 가중치가 전부 0 이상인 그래프입니다. 이제 1번 노드부터 데이크스트라 탐색 과정을 순서대로 보겠습니다. 앞서 설명했듯이 데이크스트라 탐색에는 우선순위 큐와 비용 배열(int)이 필요합니다.

 

1. 모든 노드에 대해 최소 비용을 무한대 값으로 초기화

 

처음엔 모든 노드로 이동하는 비용을 INFINITY 값으로 초기화해줍니다. 데이크스트라 알고리즘에서 최소 비용이 무한대라는 것은 아직 노드로 도달한 적이 없거나 노드로 도달할 수 없는 경우입니다. 하지만 아직은 그래프 탐색을 하기 전이므로 해당 노드에 도달한 적이 없다고 생각하면 됩니다.

 

2. 1번 노드에서 탐색 시작

 

1번 노드는 우선순위 큐에 추가합니다. 그리고 1번 노드에서 1번 노드로 이동하는 비용은 0 이므로 비용 배열의 1번 인덱스를 0으로 저장합니다.

 

1번 노드를 추출한 뒤 1번 노드와 인접한 2, 3, 6번 노드를 우선순위 큐에 추가합니다. 각각의 가중치는 4, 2, 7이므로 우선순위 큐에는 3→2→6번 순으로 삽입됩니다.

 

지금은 처음이라서 그냥 우선순위 큐에 추가한 것 같지만 정확한 로직은 다음과 같습니다. 1번 노드에서 이동가능한 노드는 2, 3, 6번 노드입니다. 1번에서 2번 노드로 이동할 때의 현재 최소 비용을 의미하는 cost[1] = ∞입니다. 그리고 1번 노드에서 2번 노드로 이동하는 비용 + 1번 노드까지 오는 데 필요했던 비용 = 4 + 0 = 4입니다. 후자의 값이 전자의 값보다 작기(미만이기) 때문에 cost[2]의 값은 ∞가 아니라 4입니다. 나머지 3번, 6번 노드도 마찬가지입니다. 3번 노드로 이동하는 비용이 각각 2, 7인데 모두 ∞보다 작으므로 cost[3]과 cost[6]의 값을 2, 7로 갱신합니다.

 

이제 살짝 감이 오시나요? 현재 저장된 최소 비용보다 새롭게 계산된 최소 비용이 더 작은 경우에만 갱신하는 구조입니다. 이어서 보겠습니다.

 

3. 우선순위 큐에서 3번 노드를 추출해서 탐색 시작

 

우선순위 큐에서 3번 노드를 추출합니다. 3번 노드는 4번 노드와 인접합니다. 그런데 4번 노드의 현재 최소 비용이 ∞이므로 2+6=8로 cost[4]의 값을 갱신해줍니다.

 

4. 우선순위 큐에서 2번 노드를 추출해서 탐색 시작

 

2번 노드를 추출합니다. 2번 노드는 4, 5, 6번 노드와 인접했지만 4번 노드로 이동하는 최소 비용이 이미 8이고 현재 4번 노드로 이동하려는 비용은 4+5=9이므로 최소 비용이 아닙니다. 따라서 우선순위 큐에 추가하지 않고 건너뜁니다. 6번 노드도 마찬가지입니다. 이미 최소 비용이 7로 저장되어 있으므로 우선순위 큐에 추가할 필요가 없습니다. 하지만 5번 노드의 경우 아직 한 번도 방문한 적이 없기 때문에 이동 비용이 무한대이고, 따라서 cost[5]는 5로 갱신됩니다.

 

5. 우선순위 큐에서 5번 노드를 추출해서 탐색 시작

 

우선순위 큐에서 5번 노드를 추출하고 인접한 노드를 탐색합니다. 7번 노드로만 이동할 수 있고, 7번 노드는 아직 방문한 적이 없기에 cost[7]은 5+3=8로 갱신됩니다.

 

6. 우선순위 큐에서 6번 노드를 추출해서 탐색 시작

 

우선순위 큐에서 6번 노드를 추출했습니다. 6번 노드와 인접한 9번 노드는 현재 최소 비용이 무한대이기 때문에 현재까지의 최소 비용 7과 9번 노드로 이동하는 비용 8의 합인 15로 갱신됩니다.

 

7. 우선순위 큐에서 4번 노드를 추출해서 탐색 시작

 

4번 노드를 우선순위 큐에서 추출했습니다. 4번 노드는 8번 노드로 이동할 수 있고, 그 비용은 8+2=10이므로 더 적은 비용으로 이동할 수 있습니다. 최소 비용 순으로 정렬되므로 우선순위 큐의 2번째에 삽입됩니다.

 

8. 우선순위 큐에서 7번 노드를 추출해서 탐색 시작

 

7번 노드를 추출했습니다. 7번 노드에선 8번 노드와 9번 노드로 이동할 수 있습니다. 8번 노드로 이동하는 최소 비용은 이미 10이기 때문에 스킵됩니다. 7번 노드까지 도달하는데 드는 비용 8과 7번 노드에서 9번 노드로 이동하는데 드는 비용 3을 더하면 11이므로 기존의 15보다 작습니다. 따라서 cost[9]=11로 갱신됩니다.

 

9. 우선순위 큐에서 8번 노드를 추출해서 탐색 시작

 

8번 노드를 추출했고, 8번 노드에서 9번 노드로 이동할 수 있습니다. 10+4=14는 기존의 비용 11보다 작기 때문에 우선순위 큐에 삽입되지 않고 스킵됩니다.

 

10. 남은 9번 노드는 이동가능한 정점 없음

우선순위 큐에 9번 노드가 2개 남았습니다. 9번 노드에선 이동가능한 정점이 없기 때문에 추출만 되고 스킵됩니다.

 

 

데이크스트라 실제 구현 코드

위에서 다뤘던 예제를 바탕으로 최소 비용을 구할 수 있도록 자바 코드로 작성해보겠습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_Dijkstra {
    static final int INF = Integer.MAX_VALUE;

    static int size, edge, start;
    static List<List<int[]>> list = new ArrayList<>();
    static int[] cost; // 또는 dist

    static int dx[] = {1, -1, 0, 0};
    static int dy[] = {0, 0, 1, -1};

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

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        size = Integer.parseInt(st.nextToken()); // 노드의 수
        edge = Integer.parseInt(st.nextToken()); // 간선의 수
        start = Integer.parseInt(st.nextToken()); // 탐색을 시작하 정점

        cost = new int[size+1];
        for(int i = 0; i <= size; i++) {
            Arrays.fill(cost, INF); // 비용 배열 초기화
        }

        for(int i = 0; i <= size; i++) {
            list.add(new ArrayList<>()); // 인접 리스트 초기화
        }

        for(int i = 0; i < edge; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            list.get(s).add(new int[] {e, c});
        }

        dijkstra(start);

        for(int i = 1; i <= size; i++) {
            System.out.println(i+" >> "+cost[i]);
        }
    }

    public static void dijkstra(int start) {
        // 우선순위 큐의 정렬 기준은 노드까지 필요한 가중치(최소 보장 X)
        Queue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);

        pq.offer(new int[] {start, 0});
        cost[start] = 0;

        while(!pq.isEmpty()) {
            int[] poll = pq.poll();

            for(int[] out : list.get(poll[0])) {
                // cost[out[0]] : 인접한 노드로 이동하는 현재 최소 비용
                // poll[1] : 탐색 중 쌓인 가중치 = 비용
                // out[1] : 현재 노드에서 인접 노드로 이동하는 가중치 = 비용
                if(cost[out[0]] > poll[1] + out[1]) {
                    cost[out[0]] = poll[1] + out[1];
                    pq.offer(new int[] {out[0], poll[1]+out[1]});
                }
            }
        }
    }
}

 

코드가 길어서 주석으로 설명을 작성했습니다. 코드의 가장 핵심은 우선순위 큐를 정렬하는 것과 while 문 내부 로직입니다. 위의 데이크스트라 알고리즘은 격자 그래프에도 응용할 수 있고, 다양한 변형이 가능합니다.

 

무한대 값의 최소값?

앞선 설명에서 dist 또는 cost 배열을 무한대 값으로 초기에 저장한다고 했습니다. 이때 무한대 값의 크기는 적어도 정점의 수 * 간선의 최대 가중치 값보다 큰 수여야 합니다.

 

 

.

.

.

 

마치며

데이크스트라 알고리즘을 익히기 위한 문제를 난이도 순으로 정리했습니다.