본문 바로가기
CS/알고리즘

[알고리즘] 다익스트라

tkxx_ls 2024. 7. 31. 23:47

다익스트라 알고리즘(Dijkstra's algorithm)은 가중치가 있는 그래프에서 시작 노드로부터 다른 모든 노드까지의 최단 경로를 찾기 위한 알고리즘입니다.

다익스트라의 특징

  • 가중치 그래프: 다익스트라 알고리즘은 가중치가 양수인 그래프에서만 성립합니다. 음수 가중치를 가진 간선이 있는 그래프에서는 다익스트라 알고리즘이 올바른 결과를 보장하지 않습니다. 이는 알고리즘의 근본적인 동작 방식이 간선의 가중치가 양수일 때만 성립하기 때문입니다.
  • 단일 출발점: 다익스트라 알고리즘은 특정 출발점에서 시작하여 다른 모든 노드까지의 최단 경로를 찾습니다. 다수의 출발점에서의 최단 경로 탐색은 여러 번의 다익스트라 알고리즘을 실행하거나 다른 알고리즘을 사용해야 합니다.
  • 그리디 알고리즘: 이 알고리즘은 기본적으로 그리디 알고리즘입니다. 즉, 현재 시점에서 가장 작은 거리를 선택하고 이를 기반으로 경로를 확장해 나가는 방식입니다.

다익스트라 동작 방법

  1. 모든 노드를 방문하지 않은 상태로 표시합니다.
    모든 방문하지 않은 노드의 집합을 "미방문 집합"이라고 부릅니다.
     
  2. 모든 노드에 시작점으로부터의 거리를 할당합니다.
    시작 노드의 거리는 0으로 설정하고, 다른 모든 노드의 거리는 무한대로 설정합니다. 이는 초기에는 이러한 노드로의 경로가 알려져 있지 않기 때문입니다. 알고리즘 실행 중에, 노드 N의 거리는 시작 노드와 N 사이에서 지금까지 발견된 최단 경로의 길이를 나타냅니다.
     
  3. 미방문 집합에서 현재 노드를 선택합니다.
    이 노드는 가장 작은 유한한 거리를 가진 노드여야 합니다. 초기에는 거리가 0인 시작 노드가 선택됩니다. 만약 미방문 집합이 비어 있거나, 무한대의 거리만을 가진 노드들로만 구성되어 있다면(즉, 도달할 수 없는 경우), 알고리즘은 6단계로 이동하며 종료합니다. 특정한 목표 노드로의 경로만 관심이 있다면, 현재 노드가 목표 노드인 경우 여기서 종료할 수 있습니다. 그렇지 않다면 도달 가능한 모든 노드에 대한 최단 경로를 찾기 위해 계속 진행합니다.
     
  4. 현재 노드의 인접한 미방문 노드들의 거리를 현재 노드를 통해 업데이트합니다.
    새로 계산된 거리와 인접한 미방문 노드에 할당된 거리를 비교하여 더 작은 값을 할당합니다. 예를 들어, 현재 노드 A의 거리가 6이고, 이웃 노드 B와 연결된 간선의 길이가 2라면, A를 통해 B로 가는 거리는 6 + 2 = 8이 됩니다. 만약 B가 이전에 8보다 큰 거리로 표시되어 있었다면, 이를 8로 업데이트합니다(A를 통해 B로 가는 경로가 더 짧기 때문입니다). 그렇지 않다면 현재 거리를 유지합니다(A를 통해 B로 가는 경로가 최단이 아니기 때문입니다).
     
  5. 현재 노드의 모든 인접한 미방문 노드들에 대한 갱신이 끝났다면, 현재 노드를 방문한 것으로 표시하고 미방문 집합에서 제거합니다.
    이는 방문한 노드를 다시 확인하지 않기 위함이며, 이는 현재 노드에 기록된 거리가 최소임이 보장되기 때문입니다(3단계에서 보장됨). 그 후 3단계로 돌아갑니다.
     
  6. 루프가 종료되면(3–5단계), 모든 방문한 노드는 시작 노드로부터의 최단 거리를 포함하게 됩니다.

 

오리지널 다익스트라 구현

다익스트라 알고리즘 초창기에는 우선순위 큐가 발전하지 않았습니다.

다음은 우선순위 큐를 사용하지 않고 구현한 다익스트라입니다.

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

public class Main {

    static class Node {
        int v; // 노드 번호
        int cost; // 가중치

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

    // 각 노드에 연결된 노드에 대한 정보를 담는 리스트
    static ArrayList<Node>[] graph;
    // 방문 여부를 체크하는 배열
    static boolean[] visit;
    // 최단 거리 테이블
    static int[] dist;

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

        int v = Integer.parseInt(st.nextToken());
        int e = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(br.readLine());

        graph = new ArrayList[v + 1];
        dist = new int[v + 1];
        visit = new boolean[v + 1];

        for (int i = 1; i <= v; i++) {
            graph[i] = new ArrayList<>();
            dist[i] = Integer.MAX_VALUE; // 최단 거리를 찾기 위해 초기값을 무한대로 설정
        }

        for (int i = 0; i < e; i++) {
            st = new StringTokenizer(br.readLine());
            int inputU = Integer.parseInt(st.nextToken());
            int inputV = Integer.parseInt(st.nextToken());
            int inputW = Integer.parseInt(st.nextToken());

            graph[inputU].add(new Node(inputV, inputW));
        }

        // 다익스트라 알고리즘 수행
        dijkstra(k);

        for (int i = 1; i <= v; i++) {
            System.out.println(dist[i] == Integer.MAX_VALUE ? "INF" : dist[i]);
        }
    }

    static void dijkstra(int start) {
        // 시작 노드에 대해 초기화
        dist[start] = 0;

        for (int i = 0; i < dist.length - 1; i++) { // 모든 노드에 대해 반복
            int minDist = Integer.MAX_VALUE;
            int minNode = -1;

            // 방문하지 않은 노드 중에서 가장 최단 거리가 짧은 노드 선택
            for (int j = 1; j < dist.length; j++) {
                if (!visit[j] && dist[j] < minDist) {
                    minDist = dist[j];
                    minNode = j;
                }
            }

            // 더 이상 방문할 노드가 없으면 종료
            if (minNode == -1) {
                break;
            }

            // 선택된 노드를 방문 처리
            visit[minNode] = true;

            // 선택된 노드와 인접한 노드들의 거리 갱신
            for (Node next : graph[minNode]) {
                if (!visit[next.v] && dist[next.v] > dist[minNode] + next.cost) {
                    dist[next.v] = dist[minNode] + next.cost;
                }
            }
        }
    }
}

우선순위 큐 다익스트라 구현

미방문 노드들 중에서 가장 작은 노드를 선택할 때 (다익스트라 동작 방법 3단계) 우선순위 큐를 사용하여 선택할 수 있게 합니다.

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

public class Main {

    static class Node implements Comparable<Node> {
        int v; // 노드 번호
        int cost; // 가중치

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

        @Override
        public int compareTo(Node other) {
            return this.cost - other.cost; // 가중치를 기준으로 오름차순 정렬
        }
    }

    // 각 노드에 연결된 노드에 대한 정보를 담는 리스트
    static ArrayList<Node>[] graph;
    // 방문 여부를 체크하는 배열
    static boolean[] visit;
    // 최단 거리 테이블
    static int[] dist;

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

        int v = Integer.parseInt(st.nextToken());
        int e = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(br.readLine());

        graph = new ArrayList[v + 1];
        dist = new int[v + 1];
        visit = new boolean[v + 1];

        for (int i = 1; i <= v; i++) {
            graph[i] = new ArrayList<>();
            dist[i] = Integer.MAX_VALUE; // 최단 거리를 찾기 위해 초기값을 무한대로 설정
        }

        for (int i = 0; i < e; i++) {
            st = new StringTokenizer(br.readLine());
            int inputU = Integer.parseInt(st.nextToken());
            int inputV = Integer.parseInt(st.nextToken());
            int inputW = Integer.parseInt(st.nextToken());

            graph[inputU].add(new Node(inputV, inputW));
        }

        // 다익스트라 알고리즘 수행
        dijkstra(k);

        for (int i = 1; i <= v; i++) {
            System.out.println(dist[i] == Integer.MAX_VALUE ? "INF" : dist[i]);
        }
    }

    static void dijkstra(int start) {
        // 우선순위 큐를 사용하여 가중치를 기준으로 최소값을 가진 노드를 우선 선택
        PriorityQueue<Node> pq = new PriorityQueue<>();
        dist[start] = 0;
        pq.add(new Node(start, 0));

        while (!pq.isEmpty()) {
            Node current = pq.poll();
            int currentNode = current.v;

            // 이미 처리된 노드는 무시
            if (visit[currentNode]) continue;

            // 현재 노드를 방문 처리
            visit[currentNode] = true;

            // 인접 노드 확인
            for (Node next : graph[currentNode]) {
                if (!visit[next.v] && dist[next.v] > dist[currentNode] + next.cost) {
                    dist[next.v] = dist[currentNode] + next.cost;
                    pq.add(new Node(next.v, dist[next.v]));
                }
            }
        }
    }
}

다익스트라 시간복잡도

우선순위 큐를 사용한 경우와 사용하지 않은 경우의 시간 복잡도를 비교해 보겠습니다.

1. 우선순위 큐를 사용하지 않은 경우

  • 알고리즘 구조: 모든 노드에 대해 가장 짧은 거리를 가진 노드를 선형 탐색으로 찾습니다.
    그 후, 해당 노드의 인접 노드들을 업데이트합니다.
  • 시간 복잡도
    • 노드의 수를 V, 간선의 수를 E라고 하면, 각 단계에서 모든 노드를 순회하면서
      최단 거리를 가진 노드를 찾는 데 O(V)의 시간이 걸립니다.
    • 그 후, 해당 노드의 인접 노드들을 업데이트하는 데 O(E)의 시간이 걸립니다.
    • 이를 모든 노드에 대해 반복하므로, 전체 시간 복잡도는 O(V2+E)입니다.
    • E가 V2보다 작은 경우, O(V2)로 단순화됩니다.

2. 우선순위 큐를 사용한 경우

  • 알고리즘 구조: 우선순위 큐(Priority Queue)를 사용하여 가장 짧은 거리를 가진 노드를 찾습니다.
  • 시간 복잡도
    • 노드를 큐에서 꺼내는 연산과 큐에 삽입하는 연산이 각각 O(log⁡V)의 시간 복잡도를 가집니다.
    • V개의 노드를 큐에서 꺼내야 하므로, 노드를 큐에서 꺼내는 데 드는 시간은 O(Vlog⁡V)입니다.
    • 또한, 각 간선에 대해 큐에 새로운 노드를 삽입하는 연산을 수행해야 하므로 간선의 수만큼 큐 연산이 발생하여 O(Elog⁡V)의 시간이 소요됩니다.
    • 전체 시간 복잡도는 O((V+E)log⁡V)가 됩니다.

따라서, 우선순위 큐를 사용해서 다익스트라를 구현하는 것이 더 빠릅니다.

'CS > 알고리즘' 카테고리의 다른 글

[알고리즘] KMP 알고리즘  (0) 2024.09.01
[알고리즘] 라빈-카프 알고리즘  (0) 2024.08.29
[알고리즘] 오일러 피  (0) 2024.06.26
[알고리즘] 소수 구하기  (0) 2024.06.18
[알고리즘] LCM  (0) 2024.06.13

'CS/알고리즘' Related Articles

티스토리툴바