[알고리즘] 다익스트라 알고리즘 (Dijkstra Algorithm) 동작 원리 및 구현하기

 다익스트라 알고리즘

 개요

• 다익스트라(dijkstra) 알고리즘은 그래프에서 한 정점(노드)에서 다른 정점까지의 최단 경로를 구하는 알고리즘 중 하나이다.
• 이 과정에서 도착 정점(노드) 뿐만 아닌, 다른 정점까지 최단 경로로 방문하여 각 정점까지의 최단 경로를 모두 찾게 된다.
• 매번 최단 경로의 정점을 선택해 탐색을 반복한다.
• 그래프 알고리즘 중 최단 거리, 최소 비용을 구하는 알고리즘은 다익스트라 외에 벨만-포드 알고리즘, 프로이드 워샬 알고리즘 등이 있다.

 

 동작 단계

1. 출발 노드와 도착 노드를 설정한다.
2. '최단 거리 테이블' 을 초기화한다.
3. 현재 위치한 노드의 인접 노드 중 방문하지 않은 노드를 구별하고, 방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택한다. (선택한 노드는 방문 처리한다.)
4. 해당 노드를 거쳐 다른 노드로 넘어가는 간선 비용(가중치)을 계산해 '최단 거리 테이블'을 업데이트 한다.
5. (3) ~ (4) 과정을 반복한다.

'최단 거리 테이블'은 1차원 배열로, N개 노드까지 오는 데 필요한 최단 거리를 기록하며, N개 크기의 배열을 선언하고 무한 값으로 초기화한다. 일반적으로 Integer.MAX_VALUE 로 초기화해도되지만, int 범위 이상의 값을 사용한다면 더 큰 값으로 잡아야한다. (이 글에서는 범위 내로 가정하고 MAX_VALUE로 사용하겠다.)

'방문 여부 테이블'은 방문한 노드인지 기록하기 위한 배열로, '최단 거리 테이블'과 동일한 크기의 배열이며 False 로 초기화한다.

 

 동작 예

 

 

 

 

 

 

 

 

 

 

 

출처 : 안경잡이개발자

 

위와 같은 그래프가 있을 때, 각 정점(노드)에서 특정 정점(노드)로의 거리를 이차원 배열 형태로 처리해준다.

이차원 배열 형태인 아래 표의 의미는 특정 행에서 열로 가는 거리(비용) 이다.

예) 1행 2열 (1에서 2로 가는 거리) : 2  

* 인덱스는 1부터 시작한다고 가정하며, 자기 자신에게 가는 거리(비용)는 0 이다.

 

정점(노드) 번호	1	2	3	4	5	6
1	0	2	5	1	MAX_VALUE	MAX_VALUE
2	2	0	3	2	MAX_VALUE	MAX_VALUE
3	5	3	0	3	1	5
4	1	2	3	0	1
5	MAX_VALUE	MAX_VALUE	5	1	0	2
6	MAX_VALUE	MAX_VALUE	5		2	0

그럼 위의 데이터를 바탕으로, 1 정점(노드)에서 6 정점(노드)로 가는 최단 거리를 구해보자.

 

1. 출발 노드와 도착 노드 설정

- 출발 노드 : 1

- 도착 노드 : 6

 

2. '최단 거리 테이블' 초기화

- 1번 정점에서 각 정점으로의 최소 비용은 다음과 같다. 연결되지 않은 간선은 MAX 값으로 유지한다.

- 1번 노드는 방문 처리한다.

 

0

2

5

1

MAX_VALUE

MAX_VALUE

 

3-1. 현재 위치한 노드의 인접 노드 중 방문하지 않은 노드를 구별하고, 방문하지 않은 노드 중 거리가 가장 짧은 노드 선택(선택한 노드는 방문 처리)

- 현재 위치 : 1

- (방문하지 않은 노드 중) 가장 짧은 노드 선택 : 4

 

4-1. 해당 노드를 거쳐 다른 노드로 넘어가는 간선 비용(가중치)을 계산해 '최단 거리 테이블'을 업데이트 한다.

- 해당 노드 : 4

- (방문하지 않은 노드 중) 연결된 노드(비용) : 2(2), 3(3), 5(1)

  노드 2 : 노드 4까지의 최소비용 (1) + 노드 4에서 노드 2까지의 최소비용 (2) = 3 

               노드 1에서 노드 2로 가는 최소 비용 (2) 보다 크기 때문에, 최소 비용을 그대로 유지해준다.

  노드 3 : 노드 4까지의 최소비용 (1) + 노드 4에서 노드 3까지의 최소비용 (3) = 4

               노드 1에서 노드 3로 가는 최소 비용 (5) 보다 작기 때문에, 최소 비용을 업데이트해준다.

  노드 5 : 노드 4까지의 최소비용 (1) + 노드 4에서 노드 5까지의 최소비용 (1) = 2

               노드 1에서 노드 5로 가는 최소 비용 (무한) 보다 작기 때문에, 최소 비용을 업데이트해준다.

 

0

2

4

1

2

MAX_VALUE

 

3-2. 현재 위치한 노드의 인접 노드 중 방문하지 않은 노드를 구별하고, 방문하지 않은 노드 중 거리가 가장 짧은 노드 선택(선택한 노드는 방문 처리)

- 현재 위치 : 4

- (방문하지 않은 노드 중) 가장 짧은 노드 선택 : 2

 

4-2. 해당 노드를 거쳐 다른 노드로 넘어가는 간선 비용(가중치)을 계산해 '최단 거리 테이블'을 업데이트 한다.

- 해당 노드 : 2

- (방문하지 않은 노드 중) 연결된 노드(비용) : 3(3)

  노드 3 : 노드 2까지의 최소비용 (2) + 노드 2에서 노드 3까지의 최소비용 (3) = 5 

               노드 3까지의 가는 최소 비용 (4) 보다 크기 때문에, 최소 비용을 그대로 유지해준다.

 

0

2

4

1

2

MAX_VALUE

 

3-3. 현재 위치한 노드의 인접 노드 중 방문하지 않은 노드를 구별하고, 방문하지 않은 노드 중 거리가 가장 짧은 노드 선택(선택한 노드는 방문 처리)

- 현재 위치 : 2

- (방문하지 않은 노드 중) 가장 짧은 노드 선택 : 5

 

4-3. 해당 노드를 거쳐 다른 노드로 넘어가는 간선 비용(가중치)을 계산해 '최단 거리 테이블'을 업데이트 한다.

- 해당 노드 : 5

- (방문하지 않은 노드 중) 연결된 노드(비용) : 3(1), 6(2)

  노드 3 : 노드 5까지의 최소비용 (2) + 노드 5에서 노드 3까지의 최소비용 (1) = 3 

               노드 3까지의 가는 최소 비용 (4) 보다 작기 때문에, 최소 비용을 업데이트해준다.

  노드 6 : 노드 5까지의 최소비용 (2) + 노드 5에서 노드 6까지의 최소비용 (2) = 4 

               노드 3까지의 가는 최소 비용 (무한) 보다 작기 때문에, 최소 비용을 업데이트해준다.

 

0

2

3

1

2

4

 

3-4. 현재 위치한 노드의 인접 노드 중 방문하지 않은 노드를 구별하고, 방문하지 않은 노드 중 거리가 가장 짧은 노드 선택(선택한 노드는 방문 처리)

- 현재 위치 : 5

- (방문하지 않은 노드 중) 가장 짧은 노드 선택 : 3

 

4-4. 해당 노드를 거쳐 다른 노드로 넘어가는 간선 비용(가중치)을 계산해 '최단 거리 테이블'을 업데이트 한다.

- 해당 노드 : 3

- (방문하지 않은 노드 중) 연결된 노드(비용) : 6(5)

  노드 6 : 노드 3까지의 최소비용 (3) + 노드 3에서 노드 6까지의 최소비용 (5) = 8 

               노드 6까지의 가는 최소 비용 (4) 보다 크기 때문에, 최소 비용을 그대로 유지해준다.

 

0

2

3

1

2

4

 

3-5. 현재 위치한 노드의 인접 노드 중 방문하지 않은 노드를 구별하고, 방문하지 않은 노드 중 거리가 가장 짧은 노드 선택(선택한 노드는 방문 처리)

- 현재 위치 : 3

- (방문하지 않은 노드 중) 가장 짧은 노드 선택 : 6

 

4-5. 해당 노드를 거쳐 다른 노드로 넘어가는 간선 비용(가중치)을 계산해 '최단 거리 테이블'을 업데이트 한다.

- 해당 노드 : 6

- (방문하지 않은 노드 중) 연결된 노드 : 없음

 

0

2

3

1

2

4

 

더 이상 방문할 노드가 없음으로 최종 배열은 위와 같이 형성된다.

정점(노드) 1 에서 정점(노드) 6 으로 가는 최소 비용은 4가 나오는 것을 알 수 있다.

 

 특징

• 방문하지 않은 노드 중 최단 거리인 노드를 선택하는 과정이 반복된다.
• 도착 노드는 해당 노드를 거쳐 다른 노드로 가는 길을 찾을 필요는 없다.
• 다익스트라 알고리즘은 가중치가 양수일 때만 사용 가능하다.

 

구현 방법

방문하지 않은 노드를 탐색하는 과정에서 구현 방법이 두 가지로 나뉜다.

• 순차 탐색
• 우선순위 큐

순차 탐색의 경우 (N * N) 개의 인접행렬 을 만들어, 거리 테이블의 앞에서부터 노드의 개수만큼 순차적으로 탐색을 수행하는 방식으로, 노드의 개수가 N일 때, O(N²)의 시간복잡도가 걸린다.

반면, 우선순위 큐는 리스트 형태의 최소 힙으로 구현하며, 매번 루트 노드에 '시작 노드로부터 가장 가까운 노드'가 된다.

순차 탐색과는 다르게 방문 여부를 기록할 배열을 가지고 있지 않아도 된다.

간선의 수를 E(Edge), 노드의 수를 V(Vertex)라고 했을 때 O(ElogV) 의 시간 복잡도를 갖는다.

 

구현 예제 : 백준 최단경로 (1753)

1753번: 최단경로

 우선순위 큐 구현 예제

import java.io.*;
import java.util.*;

public class Main {

    static int V, E, K;
    static int[] dist;
    static ArrayList<Node>[] graph;    // 정점 간의 거리를 담을 초기 테이블
    static final int INF = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        //System.setIn(new FileInputStream(new File("src/acmicpc/input/1753.txt")));

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        V = Integer.parseInt(st.nextToken());   // 정점 개수
        E = Integer.parseInt(st.nextToken());   // 간선 개수
        K = Integer.parseInt(br.readLine());    // 시작 번호

        // 1. 누적 가중치 담을 배열 최대 값으로 초기화 (1 인덱스부터 시작하기 위해 정점 개수 + 1)
        dist = new int[V+1];
        Arrays.fill(dist, INF);

        // 2.초기 간선 가중치 정보 초기화
        graph = new ArrayList[V+1];
        for(int i = 1; i <= V; i ++) {
            graph[i] = new ArrayList<Node>();
        }

        // 3. 방향별 간선 가중치 정보 입력
        for(int e = 0; e < E; e ++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());   // a <-> b 거리 c

            graph[u].add(new Node(v,w));
            // 만약 정점간의 간선이 최대 1개 (방향이 존재하지않는) 일 경우
            // graph[v].add(new Node(u,w)); 도 같이 설정
        }

        // 4. 다익스트라 (출발지 부터 시작)
        dijkstra(K);

        // 5. 전체 출력
        for(int i = 1; i <= V; i ++) {
            bw.write((dist[i] == INF ? "INF" : dist[i]) + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }

    // 우선순위 큐를 이용한 다익스트라
    public static void dijkstra(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<Node>(); // 우선순위 큐 사용 (거리 비용이 작을 수록 우선순위)
        dist[start] = 0;    // 출발지 거리 비용 0
        pq.add(new Node(start, 0));

        while(!pq.isEmpty()) {
            Node curr = pq.poll();   // 최소 값 우선순위

            // 특정 목적지에 대착하는 문제인 경우, 도착지 도착 후 break
            // 현재 문제는, 전체를 다 돌아야하는 문제

            // 현재(curr) 가져온 간선의 거리 비용이 더 큰 경우는 패스
            if(curr.distance > dist[curr.index]) continue;

            // 현재(curr) 위치에 연결된 간선 탐색
            for(Node next : graph[curr.index]) {

                // 현재값 + 다음값 이 더 작을 때만 갱신 및 우선순위 삽입
                if(dist[next.index] > curr.distance + next.distance) {
                    dist[next.index] = curr.distance + next.distance;
                    pq.add(new Node(next.index, dist[next.index]));
                }
            }
        }
    }

    public static 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;  // 기준 값 오름차순 (우선순위는 낮은 거리)
        }
    }
}