[알고리즘] 다익스트라 알고리즘

다익스트라 알고리즘(Dijkstra Algorithms)은 그래프에서 여러 개의 노드가 있을 때, 특정 노드에서 다른 노드로 가는 최단 경로를 구해주는 알고리즘으로, 각각의 노드들 간의 가중치 (비용) 값이 음수가 아닐 때만 제대로 동작합니다.

 

다익스트라 알고리즘은 기본적으로 매번 가장 비용이 낮은 간선을 선택하기 때문에 그리디 알고리즘을 따른다고 볼 수 있습니다. 다익스트라 알고리즘은 기본적으로 다음과 같은 단계를 거칩니다.

 

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

2. distance 배열을 초기화한다.

3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.

4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다.

5. 3번과 4번 과정을 반복한다.

 

위에서도 알 수 있듯이 다익스트라 알고리즘의 구현을 위해서는 여러 배열들을 사용합니다. 

 

먼저 distance 배열은 현재 상황에서 출발지로부터 각 노드까지 가는 가장 가까운 경로를 저장하기 위한 배열이고, 추가적으로 이미 확인을 한 노드인지를 체크하기 위해 visit 배열도 사용합니다.

 

그림을 이용해서 더 자세하게 알아보겠습니다.

 

먼저 위와 같은 그래프가 존재하고, 1에서 6으로 가는 최단 경로를 알아보도록 하겠습니다.

 

우선 각각의 비용들을 이차원 배열에 저장시켜 줍니다. 그럼 다음과 같은 형태로 나타낼 수 있습니다.

 

0 1 3 0 0 0

0 0 2 2 0 0

0 0 0 0 2 0

0 0 0 0 0 9

0 0 0 8 0 1

0 0 0 0 0 0

 

visit = [f, f, f, f, f, f]

distance = [INF,INF,INF,INF,INF,INF]

 

visit 배열은 아직 아무 노드도 방문하지 않았으니 false로 초기화해주고, distance 배열은 무한대로 초기화해줍니다. 실제 구현에서는 보통 int 범위 중 최댓값을 사용합니다.

 

이제 다익스트라 알고리즘을 실행합니다. 처음 출발지인 1의 visit 값을 true로 바꿔주고, 1에서 1로 가는 비용은 당연히 0이므로 distance 값도 0으로 업데이트해줍니다. 그 뒤 1과 연결되어있는 2와 3으로 가는 비용을 distance 배열에 업데이트해줍니다.

 

visit = [t, f, f, f, f, f]

distance = [0,1,3,INF,INF,INF]

 

그 뒤 현재 가장 distance 값이 작으면서 visit이 아직 false인 노드를 찾습니다. 위의 그림에서는 2번이겠군요. 

 

visit = [t, t, f, f, f, f]

distance = [0,1,3,3,3,INF]

 

2번 노드로부터 이어진 곳들을 찾아서 위와 같이 distance 값들을 업데이트해줍니다. 4번 노드까지 가는 데 드는 비용의 합은 1->2로 갈 때 드는 1과 2->4로 갈 때 드는 2를 합쳐서 3이 됩니다. 5번도 마찬가지고요. 이런 식으로 계속 1과 직, 간접적으로 연결된 모든 노드를 방문하며 같은 연산을 반복해줍니다.

 

각 노드를 검사한 뒤의 결과는 다음과 같습니다. 검사할 노드를 고를 때는 현재 distance 값이 가장 작으면서 visit이 true인 노드를 선택해주고, 혹시 distance 값이 같으면 노드의 번호가 낮은 순서대로 검사해주면 됩니다. 

 

3번 노드 검사 후

visit = [t, t, t, f, f, f]

distance = [0,1,3,3,3,INF]

 

4번 노드 검사 후

visit = [t, t, t, t, f, f]

distance = [0,1,3,3,3,12]

 

5번 노드 검사 후

visit = [t, t, t, t, t, f]

distance = [0,1,3,3,3,4]

 

6번 노드 검사 후

visit = [t, t, t, t, t, t]

distance = [0,1,3,3,3,4]

 

따라서 distance 배열에 따라 1번에서 6번으로 가는 최소 비용은 4가 됩니다.

 

이를 자바로 구현하면 다음과 같습니다.

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
 
class Main {
 
    static int [][]arr;
    static int []distance;
    static boolean []visit;
    static int V, E, K;
 
    public static int smallest_dis(){ // 노드 중 visit이 0이고 distance가 가장 작은 노드 리턴
        int i;
        int min = Integer.MAX_VALUE;
        int min_index=0;
        for(i=1;i<=V;i++){
            if(distance[i] < min && visit[i] == false){
                min = distance[i];
                min_index = i;
            }
        }
        return min_index;
    }
 
    public static void dijkstra (int k){ // 다익스트라
 
        int i, j;
        int now;
        visit[k] = true;
        distance[K] = 0;
 
        for(i=1;i<=V;i++){
            if(arr[k][i] != 0)
                distance[i] = arr[k][i];
        }
 
        for(i=0;i<V;i++){
            now = smallest_dis();
            if(now==0)
                break;
            visit[now] = true;
            for(j=1;j<=V;j++){
                if(arr[now][j] != 0 && distance[j] > distance[now]+arr[now][j])
                    distance[j] = distance[now]+arr[now][j];
            }
        }
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int i;
        int u,v,w;
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(br.readLine());
        arr = new int[V+1][V+1];
        distance = new int[V+1];
        visit = new boolean[V+1];
        Arrays.fill(distance,Integer.MAX_VALUE);
        Arrays.fill(visit,false);
 
        for(i=0;i<E;i++){
            st = new StringTokenizer(br.readLine());
            u = Integer.parseInt(st.nextToken());
            v = Integer.parseInt(st.nextToken());
            w = Integer.parseInt(st.nextToken());
 
            arr[u][v] = w;
        }
        dijkstra(K);
        
        bw.write(String.valueOf(distance[V]));
        bw.flush();
        bw.close();
        br.close();
    }
}