다익스트라(Dijkstra)

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

  다익스트라 알고리즘이란 어떤 하나의 노드에서 다른 노드들까지 가는 최단경로를 전부 찾아내는 알고리즘이다. (출발지 고정)  백준 1753번 최단경로 문제를 풀면서 공부했다. (https://www.acmicpc.net/problem/1753)

 

 우선 알고리즘을 간략하게 보자. (문제에서 노드간의 가중치를 알려줬다는 전제에서 시작)

 배열을 만들어서 모든 노드의 cost(가중치)를 INT_MAX값으로 만든다. 그리고 출발지의 cost만 0으로 바꿔주고 출발지를 방문한다. '방문한 노드에 연결된 각각의 노드들의 cost'를 '방문한 노드와 연결된 노드 사이의 cost + 방문한 노드의 cost'와 비교하여 더 작은 값을 연결된 노드의 cost로 바꿔준다. 그리고 cost의 값이 바뀐 노드는 우선순위 큐에 넣어준다. 여기서 우선순위큐는 노드들의 cost의 값을 기준으로 오름차순으로 정렬되므로 다음 방문할 노드는 큐 안에서 cost가 가장 작은 노드가 된다. (이때 방문한 노드는 체크를 늘 하므로 한 번 방문한 노드는 다시 방문 x)

 다음으로 cost가 가장 작은 노드를 우선순위 큐에서 꺼내 방문해서 연결된 노드들과 위 과정을 반복한다. 이렇게 cost가 작은 것을 기준으로 계속 노드를 방문하다보면 결국 갈 수 있는 모든 노드들을 다 방문하게 되고 그래프 탐색이 끝난다.

 만약 방문할 수 없는 곳이 있다면 cost가 INT_MAX값으로 남아있을 것이다. 그게 아닌 방문한 곳들의 cost는 출발지에서의 최단거리로 남아있을 것이다.

시간복잡도는 인접 행렬로 구현한 경우 O(n^2)이고 위에서 설명한 것처럼 우선순위 큐를 사용한 경우 시간복잡도가 O(mlogn)까지 낮춰진다.(n = 노드(V)의 개수, m = 간선(E)의 개수)

 

 그렇다면 백준 1753번인 최단경로를 푼 Java코드를 보며 알고리즘을 이해해보자.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
class Node implements Comparable<Node>{
    int index; // 노드
    int cost; // 가중치
    Node(int i, int c) {
        index = i;
        cost = c;
    }
    @Override // 가중치를 기준으로 오름차순
    public int compareTo(Node o) {
        return this.cost - o.cost;
    }
}

class Main {
    static void dijkstra(ArrayList<Node>[] lst, int V, int K)
    {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        int[] ans = new int [V + 1];          // cost 저장
        boolean[] check = new boolean[V + 1]; // 방문 여부

        Arrays.fill(ans, Integer.MAX_VALUE); // MAX_VALUE로 초기화
        pq.offer(new Node(K, 0));
        ans[K] = 0;  // 시작노드의 cost = 0

        while (!pq.isEmpty())
        {
            int now = pq.poll().index; // 현재 방문한 노드
            if (check[now]) continue; // 방문한 곳이면 PASS (이미 더 적은 cost 값으로 방문했으므로 PASS)
            check[now] = true; // 방문 처리
            for (Node next : lst[now]) { // 방문한 노드에 연결된 노드들을 하나씩 확인 (next = 연결된 노드)
                if (ans[next.index] > ans[now] + next.cost) // cost의 최솟값이 바뀌는 경우
                {
                    ans[next.index] = ans[now] + next.cost;
                    pq.offer(new Node(next.index, ans[next.index])); // 우선순위 큐에 바뀐 cost와 노드 넣기
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= V; i++)
        {
            if (ans[i] == Integer.MAX_VALUE)
                sb.append("INF\n");
            else
                sb.append(ans[i]).append('\n');
        }
        System.out.print(sb);
    }

    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());   // 시작 노드
        ArrayList<Node>[] lst = new ArrayList[V + 1]; // 노드간의 연결관계와 cost 저장
        for (int i = 0; i <= V; i++)
            lst[i] = new ArrayList<>();
        for (int i = 0; i < E; i++)
        {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            lst[a].add(new Node(b, c));
        }
        dijkstra(lst, V, K); // 다익스트라 알고리즘 함수
    }
}

 

---

reference

- https://velog.io/@suk13574/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Java%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BCDijkstra-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98