[Java] Dijkstra Path 다익스트라 알고리즘 구현(ft. 우선순위 큐)

쉽지만 복잡한 다익스트라 알고리즘

🤔 다익스트라 알고리즘은 왜 쓸까?

❗️최단 경로를 구하는 알고리즘 중 하나이다.

 

특정 지점에서 목표 지점으로 가장 적은 비용을 들이며 가야할 때 사용할 수 있다.

예) A에서 D로 가는데 걸리는 비용은 최소 값은?

A -> D = 5

A -> B -> D = 5

A -> C -> D = 3

 

따라서 실제 최소 비용 지불하는 경로는 A -> C -> D 이다.

🥸 다익스트라 알고리즘 로직

1. 시작지점과 연결된 노드들과의 비용을 구한다.

Result List

연결된 노드	A	B	C	D	E
비용	0	3	1	5	무한

출발 지점이 A일 때, 자기 자신에게 가는 비용은 없으니 0

A에서 E와 같이 바로 연결된 경로는 없을 때, 비용을 무한(영향을 주지 않는 아주 큰 값)으로 한다.2

 

2. 가장 작은 비용을 우선순위에 담는다.

Priority Queue

우선 순위 큐	C	B	D
비용	1	3	5

우선 순위 큐는 비용이 가장 낮은 것을 우선 순위로하여 추출되는 큐이다.

우선 순위 큐에서 하나씩 추출하며 연결된 다른 노드들의 비용을 확인하고 갱신한다.

C와 연결된 노드	A	B	C	D	E
비용	-	-	-	2	-

C와 연결된 노드는 D하나 뿐이고 D까지의 비용은 2이다.

우선 순위 큐에서 꺼낸 C는 이미 1이라는 비용을 가지고 있기에 D로 가기위해서는 1 + 2라는 비용을 가지게 된다.

결과적으로 A에서 D까지가는데 3이라는 비용이 발생하고 현재 Result List의 비용(5)보다 작기에 더 작은 값으로 갱신해준다.

3의 비용이 발생하는 D까지가는 경로를 우선 순위 큐에 넣어준다.

 

Priority Queue

우선 순위 큐	D	B	D
비용	3	3	5

D와 연결된 노드는 E이고 비용은 2이기 때문에 3 + 2 = 5가 A -> E 경로의 비용이다.

현재 A -> E까지의 비용인 무한대 보다 작기 때문에 갱신하고 E까지의 경로를 우선 순위 큐에 넣어준다.

 

Result List

연결된 노드	A	B	C	D	E
비용	0	3	1	3	5

Priority Queue

우선 순위 큐	B	D	E
비용	3	5	5

이제 우선 순위 큐에서 B를 선택하고 연결된 D와의 비용을 합치면 A -> D = 5이다.

하지만 현재 Result List에 D까지의 비용은 3으로 더 작으므로 갱신되지 않고 끝이난다.

마찬가지로 다음 순서인 D를 우선 순위 큐에서 뽑아도 이미 D의 값이 5로 Result List의 D값 보다 크기 때문에 어떤 경로도 더 클 수 밖에 없기에 아무 행위를 하지 않고 끝낸다. 이렇게 E까지도 따로 갱신을 하지 않고 끝난다.

 

=> 결과적으로 최종 비용은 아래와 같이된다.(A에서 출발)

Result List

연결된 노드	A	B	C	D	E
비용	0	3	1	3	5

😏 다익스트라 알고리즘 시간 복잡도

O(E * longE): E는 Node의 간선의 수

 

최악의 경우 모든 노드를 검사하게되면, 인접한 간선을 모두 검사하므로 간선의 총 합(E)만큼 검사해야 한다.

 

이때, 우선 순위 큐에 간선만큼 할당되므로 O(logE) 만큼의 시간 복잡도를 가진다.

 

모든 간선을 검사(E) * 간선만큼 우선 순위 큐 발생(logE) => E * logE

 

🧐 다익스트라 알고리즘 자바로 구현하기

해당 알고리즘을 수행하기 위해서는 우선 순위 큐(Priority Queue) 패키지를 사용해야 합니다.

public class DijstraPath {

    public static class Node implements Comparable<Node> {  // 연결된 노드
        String vertex;  // 연결 노드의 이름
        int weight; // 가중치

        // 노드 생성자
        public Node(String vertex, int weight){
            this.vertex = vertex;
            this.weight = weight;
        }
        @Override
        public int compareTo(Node o) {
            return this.weight - o.weight;  // 가중치에 따른 오름차순 정렬(우선순위 큐의 기준도 됨)
        }
    }

    public Map<String, Integer> dijkstraFunc(Map<String, ArrayList<Node>> map, String start) {
        PriorityQueue<Node> pq = new PriorityQueue<>(); // min heap 구조의 우선순위 큐 생성
        Map<String, Integer> result = new HashMap<>();    // 시작 지점이 최종적으로 모든 정점과 연결된 최종 가중치를 저장할 변수
        Node pqNode;    // 우선순위 큐에 들어갈 노드
        ArrayList<Node> nodeList;   // 우선순위 큐에서 선택된 노드들과 연결된 노드들을 담을 배열

        // 초기화(시작점과 연결된 정점들의 가중치 적용)
        for(String key : map.keySet()){
            result.put(key, Integer.MAX_VALUE);   // 모두 최대치로 초기화
        }
        result.put(start, 0); // 자기 자신과의 거리는 0으로 초기화
        pq.add(new Node(start, 0)); // 자기 자신을 첫 우선순위 큐에 대입

        while(!pq.isEmpty()){   // 큐가 비어질 때까지 반복함

            pqNode = pq.poll(); // 우선 순위의 인자 추출(여기선 min 값)

            if(result.get(pqNode.vertex) < pqNode.weight){  // 새로 선택된 node보다 이미 더 적은 가중치라면 패스
                continue;
            }

            nodeList = map.get(pqNode.vertex); // 새로 선택한 node의 가중치가 현재보다 더 적다면 연결된 정점들과의 가중치를 비교
            for(Node searchNode : nodeList) {
                int newWeight = searchNode.weight + pqNode.weight;
                if(newWeight < result.get(searchNode.vertex)){  // 새로운 경로의 가중치가 더 적다면 갱신
                    result.put(searchNode.vertex, newWeight);
                    pq.add(new Node(searchNode.vertex, newWeight)); // 우선순위 큐에 추가
                }
            }
        }
        return result;
    }

Node 객체를 만들어 노드의 이름과 가중치를 저장한다.

 

프로퍼티가 2개(이름과 가중치 값)을 가지므로 우선 순위 큐를 사용하기 위해서 가중치를 기준으로 오름차순을 해야한다.

 

이를 위해서 Comparable 인터페이스를 사용한다.