[Algorithm] Dijkstra - 다익스트라

목표

---

• 최소비용 경로문제로 대표되는 Dijkstra 알고리즘에 대해 이해하고 학습한다.
• Dijkstra 알고리즘을 활용할 수 있는 알고리즘 문제를 풀어보고 정형화된 템플릿을 만들어보자.

 

 

Dijkstra란

---

Dijkstra

• Dijkstra란 V개의 정점과 각각의 가중치(W)를 가진 E개의 간선을 가진 그래프에서 i번 정점에서 j번 정점까지로의 최소 가중치를 가지는, 최단 경로를 찾는 알고리즘이다. 아래는 Dijkstra 알고리즘을 활용할 수 있는 그래프의 예시이다.
• Dijkstra 알고리즘을 활용하기 위해서는 앞서 설명한 그래프, 정점 별 최소 가중치를 저장하기 위한 1차원 배열, 그래프 탐색을 위한 자료구조가 필요하다. 그래프 탐색을 위한 자료구조는 인접행렬과 우선순위 큐를 사용할 수 있고, 인접행렬을 개선한 방법이 우선순위 큐를 사용하는 것이라고 한다.

 

 

 

• Dijkstra 알고리즘을 이용해 1번 정점에서 4번 정점까지 최소 가중치를 가지는 최단 경로를 찾아보자. 우선순위큐의 기본 옵션인 Min-Heap을 기준으로 현재 위치가 1번 정점일때 그래프의 상황은 다음과 같다.
• dist 배열을 보면 출발 정점이 1번 정점이기때문에 1번 Index가 0으로 초기화 되어있고, 나머지는 무한대를 표현하는 INF가 들어가있다. pq 우선순위큐에는 1번 정점에서 도달가능한 2번, 3번 정점이 간선의 가중치가 낮은 순서대로 들어와있다.

 

 

• dist[2]에 저장되어있는 값보다 1번 정점에서 2번 정점을 연결하는 간선의 가중치가 더 작기 때문에(2 < INF), dist[2]는 2로 초기화된다. 다음으로 우선순위큐에서의 다음 정점이 2번 정점이기 때문에 현재 위치를 2번 정점으로 옮기고, 2번 정점에서 도달 가능한 정점들을 우선순위큐에 다시 삽입한다.
• 여기서 중요한 부분은 우선순위큐에 들어가는 객체의 가중치 값은 지나오는 모든 간선의 가중치 합이라는 것이다. 아래 그래프를 보면 1번에서 3번 정점 경로의 가중치(3), 1번에서 2번, 3번 경로의 가중치(6), 1번에서 2번, 4번 경로의 가중치(7)을 기준으로 탐색을 진행하는것을 볼 수 있다.

 

 

• dist[3]에 저장되어있는 값보다 1번 정점과 2번 정점을 연결하는 간선의 가중치가 더 작기 때문에(3 < INF), dist[3]은 3으로 초기화된다. 이후, 현재 위치를 3번 정점으로 옮기고 다시 도달 가능한 정점들을 우선순위큐에 삽입한다. 이후로는 그래프 탐색이 모두 끝날때까지 같은 동작을 계속해서 반복하면 된다. 

 

 

• 최종적으로, Dijkstra 알고리즘을 모두 마친 그래프와 자료구조의 상황은 아래와 같아진다. 우선순위큐가 비었으니 탐색이 종료되었고, 1번 정점에서 4번 정점까지 도달하기위한 최소 가중치는 7(dist[4])인 것을 알 수 있다.

 

 

 

 

Dijkstra Code

---

• Dijkstra 알고리즘과 관련된 알고리즘 문제를 풀면서 나름대로의 템플릿을 만들어봤다. 백준 기준 골드 문제를 풀 수 있도록 만들었으며, 더 높은 레벨의 문제를 해결하기 위해서는 다른 방법 또는 조건이 필요할 수 있다.

package Algorithm;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

public class dijkstra {
    //각 정점번호와 간선의 비용정보를 담을 자료구조
    private final List<List<Node>> graph = new ArrayList<>();
    
    //출발점으로부터 i번째 정점까지의 최소비용을 기록하는 자료구조
    private int[] dist;
    
    public void dijkstra() {
        //다익스트라 탐색을 위한 자료구조
        PriorityQueue<Node> pq = new PriorityQueue<>();
        
        //시작 정점번호와 비용을 pq에 넣고 프로세스 시작
        pq.add(new Node(1, 0));
        while(!pq.isEmpty()) {
            Node node = pq.poll();
            int curNode = node.getCurNode();
            
            //그래프에서 현재 정점에서 도달 가능한 정점리스트 추출
            List<Node> nextNodes = graph.get(curNode);
            for (Node nextNode : nextNodes) {
                int cost = nextNode.getCost();
                
                //현재 정점 + 다음정점으로가는 비용과 다음 정점에 기록되어있는 비용을 비교한다.
                //다음 정점의 값이 크다면 새로운 값을 갱신하고 다음 정점 추가한다.
                if(dist[curNode] + cost < dist[nextNode.getCurNode()]) {
                    dist[nextNode.getCurNode()] = dist[curNode] + cost;
                    
                    //여기서 주의해야할 점은 pq에 기존정점를 그대로 삽입하는 것이 아니라는 것이다.
                    //지금까지 비용의 합을 비용으로 가지는 새로운 노드를 삽입해줘야한다.
                    pq.offer(new Node(nextNode.getCurNode(), dist[nextNode.getCurNode()]));
                }
            }
        }
    }
}

//정점과 간선의 가중치 정보를 가지는 Node클래스 선언
class Node implements Comparable<Node> {
    private final int curNode;
    private final int cost;
    Node(int curNode, int cost) {
        this.curNode = curNode;
        this.cost = cost;
    }
    public int getCurNode() {
        return curNode;
    }
    public int getCost() {
        return cost;
    }
    
    //우선순위큐에서 우선순위비교를 위한 함수 오버라이딩
    @Override
    public int compareTo(Node n) {
        return Integer.compare(cost, n.cost);
    }
}

 

 

해결한 문제

백준 1753번 최단경로(골드4) - https://www.acmicpc.net/problem/1753
백준 5972번 택배배송(골드 5) - https://www.acmicpc.net/problem/5972

 

 

 

 

[ 참고자료 ]

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

[알고리즘/Java]다익스트라(Dijkstra) 알고리즘