[알고리즘] 다익스트라

1. 개념

그래프에서 출발 노드와 다른 노드들 간의 최단 거리를 구하는 알고리즘이다. 즉 노드 1, 2, 3, 4, 5가 있고 출발 노드가 1이라고 했을 때, 1부터 2까지 가는 최단 거리, 1부터 3까지가는 최단거리, 1부터 4까지가는 최단 거리, 1부터 5까지 가는 최단 거리를 구할 수 있는 알고리즘이다.

 

2. 특징

• 간선의 가중치가 양수다.
• 시간 복잡도가 O(에지수log노드수) 이다.
• 우선순위 큐를 사용하여 시간복잡도를 시간 복잡도를 줄인다
  • 우선순위 큐를 사용하면 현재 위치로부터 최소 비용으로 갈 수 있는 다음 노드를 먼저 탐색하여서 불필요한 경로를 탐색하지 않아도 된다. 즉, 모든 노드를 탐색해보지 않아도 된다.
• 인접 리스트를 사용하는 것이 간단하다.

 

3. 원리

• 인접 리스트를 만든다
• 최단 거리 배열을 만든다
  • 출발 노드는 0으로 설정하고, 이외의 노드는 적당히 큰 값으로 설정한다.
• 최단 거리 배열에서 현재 값이 가장 작은 노드를 고른다.
• 위에서 고른 노드를 시작으로 그래프를 탐색한다. 이를 A라고 하자.
  • A 다음 노드를 탐색해 나가면서 최단 거리 배열을 업데이트한다. A 다음 노드를 B라고 하자. 
  • A의 최단 거리 배열의 값 + A와 B사이 간선의 가중치와 B의 최단 거리 배열의 값을 비교해서 더 작은 값으로 B의 최단 거리 배열 값을 업데이트한다.

 

4. 코드

public static void dij(){
    q.add(new Edge(K, 0));
    distance[K] = 0;

    while(!q.isEmpty()){
        Edge cur = q.poll();
        int c_v = cur.vertex;
        if(visited[c_v]) {
            continue;
        }
        visited[c_v] = true;
        for(int i = 0; i<list[c_v].size(); i++){
            Edge tmp = list[c_v].get(i);
            int next = tmp.vertex;
            int value = tmp.value;
            // distance[next]는 출발점에서 next까지 알려진 최단 거리(과거)
            // distance[c_v]+value 는 출발점에서 next까지 새롭게 계산한 최단 거리(새롭게 계산)
                // 만약 새롭게 계산한 것이 더 짧다면 업데이트를 해야 한다 그리고 해당 노드까지의 가장 짧은 거리가 새로 업뎃되었으니
                    // 해당 노드를 지나는 경로를 다시 재조사해야 한다. 그러니 큐에 넣는다
                // 만약 새롭게 계산한 것이 더 길다면 업데이트를 안 해도 된다
                    // 이는 기존에 계산한 것이 더 짧다는 것을 의미하니, 그 노드를 지나는 앞으로의 경로를 굳이 재조사하지 않아도 된다
                    // 그러니 큐에 넣지 않는다.
            if(distance[next] > distance[c_v] + value){
                distance[next] = distance[c_v] + value;
                q.add(new Edge(next, distance[next]));
            }
        }
    }
}

 

5. 관련 문제

백준 1753

GitHub - Lee-Min-Jung/coding_test_practice

백준 1916

GitHub - Lee-Min-Jung/coding_test_practice

백준 1854

GitHub - Lee-Min-Jung/coding_test_practice