[알고리즘] Dijkstra 알고리즘이란?

오늘은 하나의 그래프 내에 정점 A에서 정점 B까지 가는 최단 경로를 구하는 알고리즘 중 하나인 Dijkstra 알고리즘에 대해서 알아보겠스빈다.

 

---

Dijkstra 알고리즘이란?

앞서 말씀드린 것처럼, Dijkstra 알고리즘은 그래프 내에서 어떤 정점으로부터 다른 정점으로 갈 때의 최단 경로를 구하는 알고리즘입니다.

 

Dijkstra 알고리즘은 Dynamic Programming에 속하기도 하고 그리디 알고리즘에 속하기도 합니다.

 

Dynamic Programming(동적 계획법)

DP는 하나의 큰 문제를 작은 문제로 나누어서, 작은 문제들에 대한 해답을 이용해 큰 문제를 해결하는 하나의 문제해결 패러다임입니다.

그리디 알고리즘을 이용해 A에서 B로가는 경로를 구했다고 해봅시다. 

그러한 경로가 A -> D -> E -> B라고 해봅시다. 이렇게 되면, 우리는 사실 D에서 E로 가는 최단 경로도 구한 셈입니다. 그러니까, 결국 D -> E 경로가 최소임을 이용해서 A -> B를 구했다고 봐도 무방하죠.

 

 

그리디 알고리즘

당장 직면한 문제를 해결하기 위해 항상 최선의 방향을 선택한다는 이 알고리즘은, 당장 내가 방문한 정점에서 가장 가까운 정점을 선택하여 진행하기 때문에 그리디 알고리즘에 속합니다.

 

아마 다익스트라의 과정을 보시면 조금 더 이해가 수월해질 것입니다.

 

다익스트라 알고리즘은 출발 정점을 선택 후, 해당 정점으로부터 당장 다음에 방문할 정점까지만을 보고 모든 정점의 거리를 갱신합니다. 이러한 과정을 모든 정점에 대해 진행하여 최단 경로를 찾는 알고리즘입니다.

 

그림과 함께 과정을 알아봅시다.

위와 같은 그래프가 있습니다. 여기서 임의의 점을 시작으로 진행합니다.

다익스트라는 각 정점마다 자신의 정점에 오기까지의 weight의 합과, 자신의 정점을 오기 바로 직전의 정점을 저장하고 있습니다.

지금은 초기화 상태인데 weight는 무한대, 이전 정점은 -1로 초기화합니다.

이 점을 인지하면서 진행하면 되겠습니다.

 

저희는 0번 정점으로부터 시작해보겠습니다.

가장 처음 시작한 정점은 이전 weight의 합은 0, 이전 정점 또한 0으로 세팅해줍니다. 이제 정점 0을 기준으로 당장 다음에 갈 수 있는 정점들의 값을 업데이트 해줍니다.

 

1번 정점은 [1, 0]으로 3번 정점은 [2, 0]으로 세팅될 것입니다.

자 이제, 각 정점들 중에서 가장 적은 weight를 가지고 있는 정점을 방문하겠습니다.

아마도 1번 정점이 되겠지요. 또한 1번 정점에서 바로 접근 가능한 정점의 값들을 업데이트해줍니다.

 

1번 정점과 연결된 정점은 0, 2, 3, 4, 5번이 되겠지만 weight가 전보다 큰 weight로 갱신하면 안되기에 0번 정점과 3번 정점은 값이 갱신되지 않았습니다.

 

그럼 이제, 가장 작은 누적 가중치를 갖고 있는 정점을 선택해야하는데, 3번 정점과 4번 정점이 있습니다. 여기서는 아무거나 선택해도 상관 없습니다. 저희는 3번 정점을 선택해보죠.

 

마찬가지로 3번 정점을 방문하여 다른 값들을 갱신해줘야합니다. 하지만 0번, 1번, 4번 모두 갱신되는 값보다 더 작은 weight 값을 가지고 있으므로 업데이트되지 않게 됩니다.

 

이제 4번 정점을 방문합니다.

6번 정점 값이 갱신됐네요. 이제 그럼 가장 작은 weight를 갖는 6번을 방문합시다.

 

 

7번 정점이 갱신됐네요! 2번 정점은 같은 weight이므로 굳이 의미없는 연산량을 줄이기 위해서 갱신하지 않습니다. 이제 2번과 7번 중 2번을 방문해봅시다.

 

 

5번 노드의 값이 갱신됐습니다. 이제 7번 노드를 방문해보겠습니다.

 

갱신할 값이 없습니다. 다음 5번 정점을 방문하지만 마지막 정점이고 갱신되는 값이 없으므로 종료합니다.

이렇게 0번 노드에서부터 각 노드까지 가는데 걸리는 weight를 구했습니다.

 

 

다익스트라 알고리즘은 이러한 흐름대로 진행됩니다.

이제 코드를 통해 알아봅시다.

 

 

Dijkstra 알고리즘 구현

이제 다익스트라 알고리즘을 구현해봅시다.

 

우선 Edge 클래스부터 살펴봅시다.

public class Edge {
    int vertex;
    int adjVertex;
    int weight;

    public Edge(int vertex, int adjVertex, int weight) {
        this.vertex = vertex;
        this.adjVertex = adjVertex;
        this.weight = weight;
    }
}

이번 Edge 클래스는 양쪽 정점과 weight를 저장하게 됩니다.

 

 

이제 Dijkstra를 확인해봅시다.

import java.util.List;

public class DijkstraSP {
    public int N;
    List<Edge>[] graph;
    public int[] previous;

    public DijkstraSP(List<Edge>[] graph) {
        N = graph.length;
        this.graph = graph;
        previous = new int[N];
    }

    public int[] shortestPath(int s){
        boolean[] visited = new boolean[N];
        int[] D = new int[N];

        for(int i=0; i<N; i++){ // 초깃값 세팅
            D[i] = Integer.MAX_VALUE;
            previous[i] = -1;
        }
		// 첫 정점은 이전 정점도 0, weight도 0
        previous[s] = 0;
        D[s] = 0;

        for(int i=0; i<N; i++){
            int minVertex = -1;
            int min = Integer.MAX_VALUE;
            // 가장 작은 weight를 갖는 minVertex 찾기
            for(int j=0; j<N; j++){
                if( (!visited[j]) && (D[j] < min) ){
                    min = D[j];
                    minVertex = j;
                }
            }

            visited[minVertex] = true;
            // 찾아낸 minVertex를 통해서 노드의 값 갱신
            for (Edge e : graph[minVertex]) {
                if(!visited[e.adjVertex]){
                    int nowDistance = D[e.adjVertex];
                    int newDistance = D[minVertex] + e.weight;
                    if(nowDistance > newDistance){
                        D[e.adjVertex] = newDistance;
                        previous[e.adjVertex] = minVertex;
                    }
                }
            }
        }
        return D;
    }
}

 

 

어려운 로직은 따로 없으니 자세한 설명은 패스하도록 하겠습니다.

 

 

Dijkstra 알고리즘의 수행시간

우선 minVertex를 찾기 위해 O(n), minVertex를 찾은 후 그와 연결된 정점의 값을 갱신하기 위해 모든 간선을 방문하는 O(n).

따라서 총 O(n^2)이 소요됩니다.

 

만약 minVertex를 찾기 위해서 이진힙과 같은 자료구조를 사용하게 된다면 우선순위 큐에 들어가는 간선의 개수가 n개일 때, O(log n)의 복잡도를 갖습니다. 최악의 경우 이를 간선의 개수인 n만큼 반복하므로 O(n log(n))입니다.

통상 n < m^2입니다. (m은 정점의 개수) 따라서 O(n log(n)) = O(n log(m))이 됩니다.

 

 

Dijkstra 알고리즘의 단점

지금까지 우리는 가중치가 양수라는 가정하에 진행했습니다. 하지만 만약 가중치가 음수라면 어떻게 될까요??

 

다익스트라는 매반복마다 가능한 많은 노드의 거리를 갱신합니다. 따라서, 음수일 때는 계속해서 값이 갱신되는 현상이 발생할 것입니다.

만약 이러한 그래프가 주어져있을 때, 다익스트라 알고리즘을 이용해서 최단거리를 구하면 어떤 문제가 발생하는지 생각해보시면 좋을 것 같습니다.

---

오늘은 다익스트라 알고리즘에 대해서 배웠습니다. 최단거리를 찾는 알고리즘. 다음에는 앞서 소개드린 다익스트라 알고리즘의 단점을 보완하는 Bellman-Ford에 대해서 알아보겠습니다.