[알고리즘] 다익스트라(Dijkstra) - 최단거리 알고리즘

다익스트라(Dijkstra)

다익스트라 알고리즘은 음의 가중치(음의 간선, 음의 값)가 없는 그래프에서 최단 거리를 구하는 알고리즘입니다.

가장 짧은 경로를 찾으므로 "길 찾기" 문제에 많이 사용됩니다.

이전 다익스트라의 경우 O(n^2)의 시간복잡도를 가졌었지만,

현재는 우선순위 큐를 이용한 개선된 다익스트라 알고리즘이 탄생해 O(ElogE)의 시간복잡도를 가집니다. ( E는 Node의 간선의 수 )

만약 음의 간선이 존재한다면 "벨만-포드 알고리즘"을 활용해야 합니다.

 

다익스트라 알고리즘은 그리디 알고리즘과 다이나믹 프로그래밍 기법을 사용한 알고리즘입니다.

그 이유는 아래의 알고리즘 특징에서 설명하겠습니다.

 

다익스트라 알고리즘 특징

각 지점은 그래프에서 '노드' 또는 정점으로 표현되고 지점간 연결된 선은 그래프에서 '간선'으로 표현됩니다.

1. 출발 노드 설정
2. 현재 위치 값을 저장할 1차원 배열을 갖는다.
3. 최단 거리 노드로 이동후 현재 노드의 거리 값으로 배열 초기화. (현재 노드에서 다음 노드로 가는 거리가 다음 노드의 값보다 적으면 갱신하고 우선순위 큐에 해당 노드를 추가한다.)
4. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택 (방문 체크)
5. 해당 노드를 거쳐 다른 노드로 가는 비용 계산
6. 위 과정에서 3, 4번 반복

다익스트라 알고리즘은 최단 경로를 구하는 과정에서 각 노드에 대한 현재까지의 최단 거리" 정보를 항상 1차원 리스트에 저장하며 리스트를 계속 갱신합니다.

매번 현재 처리하고 있는 노드를 기준으로 주변 간선을 확인하기 때문에

방문하지 않은 노드 중에서 현재 최단 거리가 가장 짧은 노드를 확인해 그 노드에 대해 4번 과정을 수행한다는 점에서 그리디(탐욕법) 알고리즘으로 볼 수 있습니다.

또한, 출발 노드에서 목적지 노드로 갈 수 있는 노드들의 비용을 갱신하는점은 다이나믹 프로그래밍(DP)으로 볼 수 있습니다.

---

다익스트라 알고리즘 과정

1. 최단 거리를 구할 그래프

2. 출발지 1번 노드를 우선순위 큐에 넣고. 1번 노드의 거리 값(distance[1번 노드] )을 초기화. (출발지이므로 거리는 0)

3. 우선순위 큐에 값이 있으므로 우선순위 큐에서 값을 하나 꺼내고 해당 노드를 current에 저장하고 방문체크.

현재 노드는 1으로, 인접한 노드는 2번 노드와 3번 노드, 4번 노드가 있습니다. 

•  1번 노드 -> 2번 노드

1번 노드에서 2번 노드로 갈 경우 거리는 13으로 해당 값을 distance[2]에 갱신해주고, 해당 노드와 거리 값을 pq에 추가해줍니다.

 

• 1번 노드 -> 3번 노드

1번 노드에서 3번 노드로 갈 경우 거리는 21로 해당 값을 distance[3]에 갱신해주고, 해당 노드와 거리 값을 pq에 추가해줍니다.

 

• 1번 노드 -> 4번 노드

1번 노드에서 4번 노드로 갈 경우 거리는 42로 해당 값을 distance[4]에 갱신해주고, 해당 노드와 거리 값을 pq에 추가해줍니다.

 

4. 우선순위 큐에 값이 있으므로 우선순위 큐에서 값을 하나 꺼내고 해당 노드를 current에 저장하고 방문체크.

현재 2번 노드와 인전합 노드는, 1번 노드와 4번 노드가 있습니다.

• 2번 노드 -> 1번 노드

다음 노드 4번 distance[1]의 값은 0 입니다.

distance[2]의 값에서 1번 노드로 가는 거리는 13 + 8 = 21 입니다.

현재 노드에서 다음 노드로 가는 거리  > 다음 노드의 값 이므로, 값 갱신 X

 

• 2번 노드 -> 4번 노드

다음 노드 4번 distance[4]의 값은 42,

distance[2]의 값에서 4번 노드로 가는 거리는 13 + 17 = 30

현재 노드에서 다음 노드로 가는 거리  < 다음 노드의 값 이므로, distance[4] 값을 30으로 갱신하고, 해당 노드와 거리 값을 pq에 추가합니다.

 

5. 우선순위 큐에 값이 있으므로 우선순위 큐에서 값을 하나 꺼내고 해당 노드를 current에 저장하고 방문체크.

4번 노드와 인접한 노드는, 3번 노드가 있습니다.

• 4번 노드 -> 3번 노드

다음 노드 3번 distance[3]의 값은 21

distance[4]에서 3번 노드로 가는 거리는 30 + 6 = 36

현재 노드에서 다음 노드로 가는 거리  > 다음 노드의 값 이므로, 값 갱신 X

 

6. 우선순위 큐에 값이 있으므로 우선순위 큐에서 값을 하나 꺼내고 해당 노드를 current에 저장하고 방문체크.

3번 노드와 인접한 노드는, 4번 노드가 있습니다.

• 3번 노드 -> 4번 노드

다음 노드 4번 distance[4]의 값은 17

distance[3]에서 4번 노드로 가는 거리는 21 + 12 = 33

현재 노드에서 다음 노드로 가는 거리  > 다음 노드의 값 이므로, 값 갱신 X

 

6. 우선순위 큐에 값이 있으므로 우선순위 큐에서 값을 하나 꺼냅니다.

4번 노드는 이미 방문했으므로 pq에서 다음 값을 꺼내지만 다음 값도 4번 노드로 이미 방문했으므로 다음 값을 꺼냅니다.

하지만, pq가 비었으므로 다익스트라 알고리즘은 종료됩니다.

---

다익스트라 알고리즘 코드

여기서 List와 배열의 값에 + 1을 한 이유는 1번 노드면 index = 1, 2번 노드면 index = 2 이런식으로 보기 쉽게 표현하기 위해서 +1을 하였습니다.

그렇기 때문에 모든 반복문은 0이 아닌 1에서 시작하고, 0번째 인덱스는 버리는 값입니다.

그 외의 코드는 주석과 위의 과정 그림들을 같이 보며는 쉽게 이해되실 겁니다.

package algorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

public class Dijkstra {
    static int nodeCount = 4; // 노드 수
    static int lineCount = 9; // 정점 수 (입력값을 받지 않으므로 여기선 사용 X)
    static int start = 1; // 시작 정점
    static List<Node>[] graph = new ArrayList[nodeCount + 1];

    public static void main(String[] args) {
        for (int i = 1; i < nodeCount + 1; i++) {
            graph[i] = new ArrayList<>();
        }
        graph[1].add(new Node(2, 13));
        graph[1].add(new Node(3, 21));
        graph[1].add(new Node(4, 42));
        graph[2].add(new Node(1, 8));
        graph[2].add(new Node(4, 17));
        graph[3].add(new Node(4, 11));
        graph[4].add(new Node(3, 12));

        System.out.println("노드 연결 상태 : " + Arrays.toString(graph));

        Dijkstra(nodeCount, start);
    }

    public static void Dijkstra(int nodeCount, int start) {
        boolean[] visited = new boolean[nodeCount + 1];
        int[] distance = new int[nodeCount + 1];
        int INF = Integer.MAX_VALUE; // 무한대값

        Arrays.fill(distance, INF); // 거리 배열을 전부 무한대로 초기화
        distance[start] = 0; // 시작점의 값은 항상 0으로 시작

        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0)); // pq에 시작노드와 시작노드의 값을 넣는다.

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

            // 방문했다면 다음 큐를 꺼낸다.
            if (visited[current]) {
                continue;
            }

            // 방문하지 않은 노드를 방문 처리
            visited[current] = true;

            for (Node nextNode : graph[current]) {
                // 현재 노드의 거리 값 + 다음 노드로 가는 거리 값이 다음 노드의 값보다 작다면
                if (distance[nextNode.index] > distance[current] + nextNode.distance) {
                    // 현재 노드의 거리값을 갱신하고 pq에 해당 노드 추가
                    distance[nextNode.index] = distance[current] + nextNode.distance;
                    pq.add(new Node(nextNode.index, distance[nextNode.index]));
                }
            }
        }
        // 출력 부분
        for (int i = 1; i < nodeCount + 1; i++) {
            if (distance[i] == INF) {
                System.out.print("∞ ");
            } else {
                System.out.print(distance[i] + " ");
            }
        }
    }
}

class Node implements Comparable<Node> {
    int index;
    int distance;

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

    @Override
    // 오름차순 정렬
    public int compareTo(Node o) {
        return this.distance - o.distance;
    }

    @Override
    public String toString() {
        return String.format("%d번 노드로 가는 값 = %d", this.index, this.distance);
    }
}

 

출력

노드 연결 상태 : [null, [2번 노드로 가는 값 = 13, 3번 노드로 가는 값 = 21, 4번 노드로 가는 값 = 42], [1번 노드로 가는 값 = 8, 4번 노드로 가는 값 = 17], [4번 노드로 가는 값 = 11], [3번 노드로 가는 값 = 12]]

결과 : 0 13 21 30