다익스트라 알고리즘(Dijkstra's algorithm) - 인접 행렬

다익스트라 알고리즘(Dijkstra's algorithm)

 

 

다익스트라 혹은 데이크스트라 알고리즘 이라고부르는 이것은 도로 교통망 같은 곳에서 나타날 수 있는 그래프에서 꼭짓점 간의 최단경로를 찾는 알고리즘이다.

일반적인 다익스트라 알고리즘문제로는 한 꼭짓점을 "소스" 꼭짓점으로 고정하고 그래프의 다른 모든 꼭짓점까지의 최단경로를 찾는 알고리즘으로 최단 경로 트리를 만드는것이다. 그래프의 간선마다 가중치가 존재하고, 음의 가중치는 존재하지 않는다. 음의 가중치가 존재한다면 다익스트라를 사용할 수 없다.

구현하는 방법에는 인접행렬방식과 우선순위 큐 두가지가 있다. 먼저 다익스트라를 이해하기 위해 인정행렬이 더 간단하기 때문에 먼저 알아보자.

 

동작 과정을 간단하게 설명하자면 다음과 같다.

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

2. 출발노드에서 이웃한 노드중 거리가 가장 짧은순으로 선택해 가중치를  각 노드에 기록한다.

3. 기록한 노드중 거리가 가장 짧은 노드를 선택후 다시 방문하지 않은 이웃 노드를 탐색한다.

4. 재탐색하는 노드에는 기록된 가중치 + 간선 가중치와 기록되어있는 가중치중 작은 것을 기록한다.

5. 위 과정을 반복한다.

 

[예시]

 

먼저 위 그림을 예로 이차원 배열을 활용해 구현해보자. 

 

가중치를 가중치 인접 행렬(2차원 배열)에 저장한다. 연결되지 않은 노드는 INF를 기록한다.

	1	2	3	4	5	6
1	0	7	9	INF	INF	14
2	7	0	10	15	INF	INF
3	9	10	0	11	INF	2
4	INF	15	11	0	6	INF
5	INF	INF	INF	6	0	9
6	14	INF	2	INF	9	0

 

시작 노드인 1번 노드기준의 각 노드의 가중치를 기록한 배열이다.

1	2	3	4	5	6
0	7	9	INF	INF	14

인정합 노드인 2, 3, 6번 노드순으로 탐색해 나가면 값을 수정해보자. 먼저 가장 짧은 노드인 2번노드를 먼저 탐색해보자

 

2번노드

 

1	2	3	4	5	6
0	7	9 < 17 -> 9	INF -> 22	INF	14

2번의 인접노드중 방문하지 않은 노드인 3번 과 4번 노드를 보자

먼저 3번 노드를 보면 2번노드의 가중치(7) + 간선의 가중치(10) = 17

3번 노드의 가중치 = 9

최솟값을 찾는 것이기 때문에 3번 노드의 가중치는 그대로 9이다.

4번 노드는 INF 였지만 2번노드의 가중치(7) +간선의 가중치(15) = 22가 되어 4번 노드의 가중치는 22가 기록된다.

탐색이 끝났다면 1번의 인접노드 2, 3, 6 중 그 다음 노드인 3번 노드로 넘어간다.

 

3번 노드

 

1	2	3	4	5	6
0	7	9	22 -> 20	INF	14 -> 11

3번노드의 인접노드중 방문 하지 않은 노드 4번 노드, 6번 노드를 보자

3번 노드의 가중치(9) + 간선의 가중치(11) = 20

3번 노드의 가중치(9) + 간선의 가중치(2) = 11

그다음 노드 6번 노드를 탐색해보자

 

6번 노드

 

1	2	3	4	5	6
0	7	9	20	INF -> 20	11

 

6번노드의 인접노드중 방문하지 않은 노드인 4번 노드를 보자

6번 노드의 가중치(11) + 간선의 가중치(9) = 20

원래 5번의 가중치는 INF 였기때문에 더 짧은 가중치인 20으로 수정된다.

마지막 방문하지 않은 노드인 4번 노드를 확인해보자

 

4번 노드

 

 

1	2	3	4	5	6
0	7	9	20	20	11

4번노드에서 방문하지 않은 인접노드 5번노드까지를 보면

4번 노드의 가중치(20) + 간선의 가중치(6) = 26 이므로

값을 수정하지 않고 원래의 가중치인 20으로 남겨둔다.

5번 노드는 인접한 모든 노드가 방문을 완료한 노드기 때문이 탐색을 종료한다.

 

최종적인 가중치 기록 배열을 보자

1	2	3	4	5	6
0	7	9	20	20	11

 

1번 노드 -> 1번 노드 : 0

1번 노드 -> 2번 노드 : 7

1번 노드 -> 3번 노드 : 9

1번 노드 -> 4번 노드 : 20

1번 노드 -> 5번 노드 : 20

1번 노드 -> 6번 노드 : 11

 

[시간복잡도]

기본적인 다익스트라의 시간복잡도는 

V : 노드의 숫자, E : 간선의 숫자 라고 볼때 O(V^2) 이다.

하지만 우선순위 큐등을 사용해 이를 좀더 개선하면 O((V + E)logV) 가 나온다.

 

이 인접행렬방식을 자바 코드로 구현하자면 다음과 같다.

 

[코드]

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

public class Main {

    static int INF = Integer.MAX_VALUE;
    static int N, E; // 노드의 개수, 간선의 개수
    static int[][] Graph; // 노드들간의 가중치를 저장할 변수
    static int[] Dist; // 최단 거리를 저장할 변수
    static boolean[] Check; // 해당 노드를 방문했는지 체크할 변수
    public static void main(String[] args) throws Exception {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        N = Integer.parseInt(st.nextToken()); // 노드의 개수
        E = Integer.parseInt(st.nextToken()); // 간선의 개수
        Graph = new int[N][N];
        Dist = new int[N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                // 인접행렬 모든 값 INF 로 초기화
                Graph[i][j] = INF;
            }
        }

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            Graph[u][v] = Graph[v][u] = cost; // 양방향 간선
        }

        dijkstra(0);

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

    public static void dijkstra(int v) {
        Dist = new int[N];
        Check = new boolean[N];

        // Dist 값 초기화
        for (int i = 0; i < N; i++) {
            Dist[i] = INF;
        }

        // 시작노드값 초기화
        Dist[v] = 0;
        Check[v] = true;

        // 결과값 출력
        for (int i = 0; i < N; i++) {
            if(Dist[i] == INF) System.out.print("INF" + "\t");
            else System.out.print(Dist[i]+"\t");
        }
        System.out.println("");

        // 인접한 노드 Dist 갱신
        for (int i = 0; i < N; i++) {
            if (!Check[i] && Graph[v][i] != INF) { // 방문하지 않은 노드 && INF가 아닌경우
                Dist[i] = Graph[v][i]; //값 갱신
            }
        }

        // 결과값 출력
        for (int i = 0; i < N; i++) {
            if(Dist[i] == INF) System.out.print("INF" + "\t");
            else System.out.print(Dist[i]+"\t");
        }
        System.out.println("");

        for (int i = 0; i < N - 1; i++) {
            // 모든 노드가 true가 될때까지 해야하지만
            // 노드가 N개라면 다익스트라를 위해 반복수는 N-1 번만 하면 됨.
            int min = Integer.MAX_VALUE;
            int min_index = -1;

            // 노드 최소값 찾기
            for (int j = 0; j < N; j++) {
                if (!Check[j]) { //방문하지 않은 노드
                    if (Dist[j] < min) { // 방문하지 않은 노드중 가중치가 가장 작은 노드를 찾는다.
                        min = Dist[j];
                        min_index = j; // 가중치가 가장 작은 노드의 번호를 저장
                    }
                }
            }

            // 다른 노드를 거쳐 가는 것이 더 비용이 적은지 확인
            Check[min_index] = true; // 방문한 노드 true
            for (int j = 0; j < N; j++) {
                if (!Check[j] && Graph[min_index][j] != INF) {
                    if (Dist[min_index] + Graph[min_index][j] < Dist[j]) {
                        Dist[j] = Dist[min_index] + Graph[min_index][j];
                    }
                }
            }

            // 결과값 출력
            for (int j = 0; j < N; j++) {
                if(Dist[j] == INF) System.out.print("INF" + "\t");
                else System.out.print(Dist[j]+"\t");
            }
            System.out.println("");
        }
    }
}

[결과]

첫째줄에 노드와 간선의 수를 입력받고 그다음줄 부터 시작노드, 도착노드, 가중치 를 입력해준다.

편리하게 구현하기 위해 문제에서는 가장 작은 노드가 1번노드지만 구현할때는 0번노드로했다.

결과 값을 보면 예시에서 보여준 가중치 배열과 같은 결과값을 보여준다.