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

다익스트라(Dijkstra) 알고리즘이란?

1. 단일 시작점 최단 거리 알고리즘

• 시작점에서 다른 모든 정점까지의 최단 경로의 길이를 찾는 문제

2. 방향 그래프

• 방향 그래프를 가정으로 둔다. 
• 만약 무방향 그래프가 주어진다면 간선을 쪼개 방향 그래프로 바꿔서 생각

3. 0 이상 가중치 

• 음수 가중치가 있으면 안 된다.
• 다익스트라는 정점을 지날수록 가중치가 증가한다라는 사실을 전제하고 쓰인 알고리즘이다.
• 음수 가중치가 있다면 전제가 이전까지 계산해둔 최소가 최소라고 보장할 수 없기 때문이다.

4. BFS를 기본으로 한다. 

• BFS처럼 시작 정점에서 가까운 순서대로 방문한다. 
• 방문한 정점은 최단 거리가 정해진다. 

5. 탐욕(greedy) 알고리즘

• 다익스트라는 탐욕 알고리즘의 종류라고 볼 수 있다.
• 탐욕 알고리즘은 매 순간 최선의 선택을 고르는 알고리즘으로, 다음 선택할 정점을 선택할 때 우선순위 큐를 이용하여 매번 최단 거리 정점을 선택한다.
  • 정당성 증명시 다른 최단 거리가 있을 수 있다는 가정의 귀류법을 사용한다. 

 

기본 동작

• 알고리즘은 가중치에 따라 노드를 추가하여 최단 거리 노드집합 S를 만든다.
• 그리고, S에 연결된 노드 중 가장 작은 가중치를 갖는 정점을 집합 S에 추가한다.

 

1. 최단 거리 우선 우선순위 큐를 이용한 너비 탐색 

• 현재까지 찾은 최단 거리 집합 S에서 가까운 노드를 ( 노드 번호, 최단 거리 ) 쌍으로 우선순위 큐에 저장한다. 

 

2. dist[] 로 최단 거리 찾기

• "dist[i]: 시작 점에서 i번 노드까지의 최단 거리를 저장한 배열"을 이용
• 정점 방문할 때마다 최단 거리를 검사한다.
• 검사 시 더 짧다면 dist[i]를 더 작은 값으로 바꾼다.

 

3. dist[] 갱신

• 동작은 진행하면 dist[]값이 여러 번 줄일 수 있다.(갱신) 그러면, 갱신 전의 값 (노드 번호, 최단거리)이 우선순위 큐에 들어 있게 된다.
• 필요 없는 연산을 줄이기 위해, 우선순위 큐에서 나온 최단 거리가 dist 배열의 최단 거리보다 크다면 무시한다.
• 새로운 최단 경로를 찾았기 때문이다. 

if ( i의 이전 최단 거리 > dist[i] )

    continue;

 

 

시간 복잡도

다익스트라는 모든 간선(E)을 검사하며 정점을 우선순위 큐에 넣고 뺀다. 

1. 모든 간선을 검사할 경우. O(E)
2. 모든 간선을 검사할 때마다 우선순위 큐에 모든 정점을 삽입/삭제하는 경우. O(lgE)
3. 모든 정점 x 우선순위 큐 자체의 수행시간 O(ElgE) 
4. 대게 E는 V^2보다 작기 때문에 상한을 기준으로 O(ElgV)가 된다. 

최종적으로, O(E) + O(ElgV) = O(ElgV) 시간 복잡도가 된다. 

 

구현

    static void dijkstra() {
        
        PriorityQueue<Node> pq = new PriorityQueue<Node>();
        pq.add(new Node(start, 0));
        dist[start] = 0; 
        
        Node cur;
        Weight adjWeight;
        while(!pq.isEmpty()) {
            cur = pq.poll();
 
            // dist[cur노드]값이 cur를 넣을 당시 경로보다 더 짧다면 cur 무시 
            if(cur.cost > dist[cur.there])
                continue;
            
            // cur 와 간선으로 이어진 모든 방향에 대해
            for(int adj = 0 ; adj < weights[cur.there].size() ; adj++) {
                // 간선 가중치
                adjWeight = weights[cur.there].get(adj);
 
                // cur를 거쳐 가는 경로가 더 짧다면 dist를 갱신 후 pq에 추가 
                if(dist[adjWeight.num] > adjWeight.w + cur.cost) {
                    dist[adjWeight.num] = adjWeight.w + cur.cost;
                    pq.add(new Node(adjWeight.num, dist[adjWeight.num]));
                }
            }
        }
    }

 

 

 

+ 정점 찾은 경로 찾는법

기본적인 다익스트라는 최단 '거리'만 찾기 때문에 시작점에서 특정 도착점까지 경로를 구하려면 추가적인 작업이 필요하다. 

 

1 pre 배열 사용 

'pre[i] : 최단 경로에서 정점 i의 직전 정점를 가리키는 배열' 을 이용한다. 

기본 다익스트라를 응용하면 pre배열을 완성할 수 있다. 

 

2 다익스트라 응용 

pre를 채우기 위해서는 다익스트라에서 dist를 갱신할 때마다, pre도 갱신해주면 된다. 

 

    static void dijkstra() {
        
       
        pq.add(new Node(start, 0));
        dist[start] = 0; 
        
        Node cur;
        Weight adjWeight;
        while(!pq.isEmpty()) {
            cur = pq.poll();
 
            if(cur.cost > dist[cur.there])
                continue;
            
 
            for(int adj = 0 ; adj < weights[cur.there].size() ; adj++) {
 
                adjWeight = weights[cur.there].get(adj);
 
 
                if(dist[adjWeight.num] > adjWeight.w + cur.cost) {
                    dist[adjWeight.num] = adjWeight.w + cur.cost;
 
                    // dist를 갱신할 때, pre도 갱신해서 최단 경로 루트를 따라갈 수 있다. 
                    pre[adjWeight.num] = cur.there;
 
                    pq.add(new Node(adjWeight.num, dist[adjWeight.num]));
                }
            }
        }
    }

 

3 경로 찾기 

목적지에서 '거꾸로' 시작점까지 경로를 따라가면 된다. 

단, 목적지까지 도달 못 하는 경우가 있을 수 있으므로 예외처리했다. 

 

    static void getPath(int start, int end) {
        
        // 최단 거리가 초기값 max라면, 경로가 없기때문에 바로 종료 
        if(dist[end] == Integer.MAX_VALUE)
            return;
        
        // start부터 end까지 경로 저장 
        LinkedList<Integer> path = new LinkedList<Integer>();
        
        int preNode = pre[end];
        while(preNode != start) {
            path.addFirst(preNode);
            preNode = pre[preNode];
        }
        
        path.addFirst(start);
        
        // start부터 end까지 경로 완성 
    }

 

 

 

 

참고

- https://makefortune2.tistory.com/26

- https://goodgid.github.io/Dijkstra-Algorithm/

- https://blog.encrypted.gg/918?category=773649