[Algorithm] 다익스트라 알고리즘(Dijkstra)

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

그래프에서 여러 개의 노드가 있을 때, 한 노드에서 각 모든 노드 까지의 최단거리를 구하는 알고리즘이다. 다만 '음의 간선' 즉, 가중치가 0보다 작은 값이 아닌 경우에 정상 작동한다. 동작과정을 살펴보면 그리디 알고리즘(매번 비용이 가장 적은 노드를 선택하기 때문)과 다이나믹 프로그래밍(DP) 기법을 함께 사용한다. 이 두 단계를 반복하면서 임의의 노드에서 각 노드까지의 최단 거리를 구하게 된다.

 

• 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다. (그리디 알고리즘)
• 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신한다. (다이나믹 프로그래밍)

작동 방식에 대해서 그림으로 알아보자.

그림 1. 그래프 상태

그림 1은 주어진 그래프 상태이다. 출발점은 A, 도착점은 E라고 할 때, 초기 상태에서 방문하지 않은 노드 중 가장 비용이 적은 대상 노드는 다른 노드로 가는 간선 비용이 0인 것이 존재하지 않는다면 A이다. 그런 값이 존재한다 하더라도 초기 단계에선 A -> A 라고 정의하고 시작한다. 그리고 우리는 노드를 방문할 때마다 방문체크와 최소 비용 갱신을 할 것이다. 그래서 최소 비용을 담을 배열을 하나 만들것이다.

 

그림 2. A 노드 방문. 방문 처리된 노드는 회색으로 표시되어 있다.

그림 3. A 노드에서 인접 노드까지의 비용 계산

이제 지속적으로 방문하지 않은 노드 중 가장 비용이 적은 대상 노드는 어디인지 그 노드를 기준으로 갈 수 있는 인접 노드로의 최소 비용은 얼마인지를 모든 노드를 방문할 때까지 반복하면 된다. A 노드에서 인접노드로는 바로 갈 수 있으므로 간선 비용을 그대로 dist에 기록해준다. 하지만 만약 어떠한 노드로 가는데 이미 비용이 기록이 되어있다면 어떻게 할까? 다음 과정을 살펴보자.

 

그림 4. A 에서 C 로 가는 최소비용 구하기

핵심은 최소 비용을 구하면서 과정을 진행하는 것이라 했다. 우선 B가 선택되어 B를 방문하고 E로 가는 간선은 10이므로 A에서 B로 가는 비용 2가 더해져 12로 기록된다. A에서 B를 거쳐 C로 갔을때 비용은 9이다. A에서 직접 C로 갔을때 비용은 5이다. 이 두 값을 비교해서 최소값을 dist 배열에 갱신해야한다. 그래서 dist의 C에 해당하는 값은 5로 갱신은 이루어지지 않는다. 갱신이 되는 경우는 다음과 같다.

 

다음은 D가 선택된다. A에서 D를 거쳐 C로 갔을때 비용은 4이고 바로 갔을 때는 5이다. 따라서 C로 가는 비용은 4가 된다. 그리고 D에서 F로 가는 비용은 7이므로 A에서 D로 가는 비용이 더해져 10으로 기록된다.

 

 

C가 선택된다. C가 선택됨으로써 E, F로 가는 비용이 각각 기존에 기록됐던 비용들보다 작기 때문에 갱신된다. 다음으로는 비용이 더 적은 F가 선택된다.

 

마찬가지로 F로 거쳐 E로 가는 비용이 더 적기 때문에 갱신된다. 

 

마지막 노드인 E를 방문처리하면 더 이상 갈 수 있는 노드가 존재하지 않으므로 알고리즘은 종료하면 된다. 이제 이것을 코드로 작성해볼것이다.

---

다익스트라 알고리즘 구현

<필요 목록>

• 노드 클래스
• 한 번 방문한 곳은 방문할 수 없다. 그러므로 방문 여부 체크 배열이 필요하다.
• 각 노드 까지의 최소 비용들을 갱신하며 기록할 비용 배열이 필요하다.

구현하면서 고려해야 하는 것은 방문하지 않은 곳의 값을 항상 최소의 값으로 갱신하는 것이 목표이기 때문에 방문하지 않은 곳은 항상 매우 큰 값으로 초기화해두어야 한다. 구할 수 있다면 노드가 가질 수 있는 최대 비용을 넣으면 더욱 좋다.

최소 비용을 갖는 노드를 선택하는 과정은 최악의 경우 모든 노드를 확인해야 하므로 이것은 정점의 개수 만큼 반복하게 된다. 이는 O(V^2)의 시간복잡도가 된다. 이를 개선하기 위해 우선순위 큐를 활용하여 구현하기도 하는데 이는 O(ElogV)까지 시간복잡도를 줄일 수 있다고 한다.

(V : 정점의 개수, E : 한 정점의 주변 노드)

---

Node

class Node {
    int idx;
    int cost;

    public Node(int idx, int cost) {
        this.idx = idx;
        this.cost = cost;
    }
}

idx : 노드를 식별할 인덱스

cost : 해당 노드를 방문하는데 드는 비용

 

전체 코드

/*
sample input
5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6
 */

public class Dijkstra {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // V : 노드, E : 간선
        int V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());

        // 출발 노드
        int start = Integer.parseInt(br.readLine());

        // 1. 인접리스트를 이용한 그래프 초기화
        ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();

        // 입력값에서 노드의 번호는 1부터 시작. 따라서 0 번은 임의로 만들어 두기만 한다.
        for (int i = 0; i <= V; i++) {
            graph.add(new ArrayList<>());
        }

        // 그래프에 초기 입력값을 입력한다.
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());

            // a -> b 의 비용은 cost
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            graph.get(a).add(new Node(b, cost));
        }

        // 2. 방문 여부를 확인할 boolean 배열, start ~ end 까지의 최소 거리를 저장할 배열을 만든다.
        boolean[] visited = new boolean[V + 1];
        int[] dist = new int[V + 1];

        // 3. 최소 거리 담을 배열을 매우 큰 값으로 초기화 한다. 상황에 따라 노드가 가질 수 있는 최댓값을 넣어도 된다.
        for (int i = 0; i <= V; i++) {
            dist[i] = Integer.MAX_VALUE;
        }

        // 출발 지점은 다시 0으로 시작한다.
        dist[start] = 0;

        // 4. 다익스트라 알고리즘 진행
        // 모든 노드를 방문하면 종료. 노드 개수만큼 반복 진행
        for (int i = 0; i < V; i++) {
            // 4-1. 현재 거리 비용 중 최소 지점 선택
            int nodeIdx = 0;
            int nodeValue = Integer.MAX_VALUE;

            for (int j = 1; j <= V; j++) {
                if (!visited[j] && dist[j] < nodeValue) {
                    nodeValue = dist[j];
                    nodeIdx = j;
                }
            }

            visited[nodeIdx] = true;

            // 4-2. 해당 지점을 기준으로 인접 노드의 최소 거리 값 갱신
            for (int j = 0; j < graph.get(nodeIdx).size(); j++) {
                Node nextNode = graph.get(nodeIdx).get(j);

                // 현재 노드 값 + 현재 노드에서 인접 노드로 가는 값을 비교
                if (dist[nextNode.idx] > dist[nodeIdx] + nextNode.cost) {
                    dist[nextNode.idx] = dist[nodeIdx] + nextNode.cost;
                }
            }
        }

        for (int i = 1; i <= V; i++) {
            if (dist[i] == Integer.MAX_VALUE) {
                System.out.println("INF");
            } else {
                System.out.println(dist[i]);
            }
        }

    }
}

class Node {
    int idx;
    int cost;

    public Node(int idx, int cost) {
        this.idx = idx;
        this.cost = cost;
    }
}

 

해당 코드는 노드간 간선이 단방향인것으로 가정하고 구현되었다. 따라서 출력 결과는 아래와 같다.

---

정리

다익스트라 알고리즘의 기본 구조와 동작 원리, 코드 구현까지 해봤다. 한 노드에서 다른 노드까지의 최단 거리를 모두 구한다는 것에서 코딩 테스트에서도 빈번하게 요구하는 알고리즘이다. 다익스트라의 목적 자체는 단순하지만 구현 내용이 어찌 보면 복잡하기 때문에 한번 정리할 필요가 있다고 생각해서 정리하게 됐다.

 

최적화의 필요도 있다. 이 포스트에서 구현한 다익스트라는 다음 노드를 선택할 때 최소 비용을 갖는 노드를 찾기 위해 최악의 경우 모든 노드를 살펴봐야 한다는 점이 있다. 언급했다시피 이는 우선순위 큐를 활용해 개선할 수 있다. 다음 포스트에서 우선순위 큐를 활용한 다익스트라를 구현해볼 것이다.

 

다익스트라 알고리즘이 하나의 노드로부터 최단경로를 구하는 것이라면 모든 노드들에 대해 최단거리를 구하는 플로이드-워셜 알고리즘이 있고 다익스트라 알고리즘을 확장시킨 A* 알고리즘이 있다. 이에 대해서도 다뤄볼 예정이다.

 

---

출처

나무위키

[Java]다익스트라 알고리즘(Dijkstra Algorithm)