[알고리즘] 데이크스트라(Dijkstra)

Concept

• 그리디 알고리즘의 한 분류
• 다이나믹 프로그래밍 메모이제이션 기법 활용
  • 부분 문제 : 한 정점까지의 최단거리는 방문하는 여러개의 정점들의 최단거리로 이루어져있음.
• 주어지는 그래프에서 시작 정점으로부터 각 정점까지의 최단경로를 찾는 알고리즘

---

Feature

우선순위 큐와 거리배열(DP)을 활용하여 로직 구성.

• 한 정점 V까지의 최단거리를 구할 때 V까지로 가는 여러 정점들의 최단 거리 정보를 활용한다는 특징을 가짐.
• 가중치를 가진 그래프에서 최단거리를 구할 때 쓰이는 알고리즘
  • 음수 가중치를 가진 그래프에서는 사용불가.
• 우선순위 큐를 활용함으로써 시간복잡도 : O(N * NlogN)

---

Implement

인접 리스트를 통한 구현

• 우선 데이크스트라 소스코드를 보자.

private static int dijkstra(int start, int end) {
        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });
        int[] dp = new int[list.size()]; //거리 저장 배열
        Arrays.fill(dist, Integer.MAX_VALUE);

        pq.offer(new int[]{start,0});

        while(!pq.isEmpty()) {
            int[] cur = pq.poll();

            if(cur[0] == end) return cur[1]; //목표 정점에 도착한 경우

            for(Node n : list.get(cur[0])) {
                if(dp[n.v] > cur[1]+n.w) { //기존의 최단거리보다 더 낮을 경우에만
                    pq.offer(new int[]{n.v, cur[1] + n.w});
                    dp[n.v] = cur[1]+n.w;
                }
            }
        }
        return -1; //start -> end 까지의 경로가 존재하지 않을 경우
    }

코드 설명

• 위 코드는 start → end까지의 최단거리를 구하기 위해 두 개의 매개변수를 받아 구현.
  • start로부터 모든 정점까지의 최단거리를 구하려면 if(cur[0] == end) return cur[1]; 구문만 제거하면 됨.

1. 우선순위 큐의 거리(cur[1])에 따른 오름차순 정렬 재정의
2. 거리배열(dp)를 정점의 개수만큼 선언 및 최대값으로 초기화
3. while문을 돌면서 큐에서 꺼낸 정점과 인접해있는 정점들에 대해 dp배열의 거리와 비교해 더 최단거리일 경우에만 큐에 추가 및 dp배열 갱신

---

동작과정

가중치를 가지는 그래프

• 위와 같은 그래프에서 1 → 3으로 가는 최단거리는 6
  • 1 → 3 (거리 : 10)
  • 1 → 2 → 4 → 3 (거리 : 3+1+2 = 6)

• 1번 정점과 인접한 2(거리:3) 와 3(거리:10)이 큐에 추가되고 dp배열 갱신이 이루어짐.

• 우선순위 큐 정렬에 의해 2번 정점이 먼저 꺼내지고 인접한 4번 정점이 큐에 추가되고(거리:4) 최단 거리 갱신이 이루어짐.

• 4번 정점이 큐에서 꺼내질 때 현재 부분문제인 1→4 까지의 최단거리는 4
• 4에서 4→3 까지의 거리인 2를 더해 6과 dp[3]의 값을 비교
• 10(기존값) > 6 이므로 dp[3]이 6으로 갱신됨.

---

정리

• 데이크스트라는 알고리즘 문제 중에서 꽤나 비중있는 알고리즘 분류 중 하나이며 생각보다 개념이 쉽기 때문에 한번 제대로 알아두면 두고두고 써먹을 수 있는 알고리즘이니 정리를 한번 해보는것도 나쁘지 않음.
• 간단히 요약하자면 BFS를 알고있는 사람이라면 BFS의 PQ(우선순위 큐)버전이라 생각하는 것도 좋을 듯! (약간의 dp를 곁들인)

---

+ 추가 (25.02.02)

최근 다익스트라 알고리즘을 다시 공부하며 궁금한 점이 있어 새롭게 정리해보았다.

 

항상 다익스트라를 구현할 때 습관적으로 dist라는 거리 배열을 통해서 분기 처리를 진행했었다.

그러나 다익스트라의 특징을 다시 생각해보면 현재 방문한 정점에 대해서 최단거리임이 보장되기 때문에 일반적인 boolean 방문 체크로도 되어야하지 않을까? 라는 생각이 들었다.

(물론 각 정점까지의 모든 거리를 구할 필요가 없다는 전제에서..)

 

이렇게 생각한 이유는 다익스트라의 경우 시작 정점에서 인접한 모든 정점에 대해 탐색을 진행한다.

또한 우선순위 큐를 통해 최소 비용에 대해 먼저 탐색을 진행하게 된다. 이는 곧 현재 도착한 정점에 대해서 최소 비용이라는 명제가 됨.

 

만약 모든 정점까지의 거리를 구할 필요가 없이 단순히 두 정점 사이의 최단 거리를 구하기만 하면 된다면 거리 배열이 아닌 boolean 방문 배열을 사용해 보는것도 좋을 것 같다.

static int Dijkstra() {
        PriorityQueue<Node> pq = new PriorityQueue<>((o1,o2) -> o1.w - o2.w);
        pq.offer(new Node(start, 0));
        boolean[] v = new boolean[N+1];

        while(!pq.isEmpty()) {
            Node cur = pq.poll();

            v[cur.v] = true;
            if(cur.v == end) return cur.w;

            for(Node next : list.get(cur.v)) {
                if(v[next.v]) continue;
                pq.offer(new Node(next.v, cur.w + next.w));
            }
        }
        return -1;
    }