[알고리즘 개념] 다익스트라(Dijkstra)

개념설명

다익스트라 알고리즘은 노드와 노드의 사이 간선에 가중치가 있을 때 특정 노드에서 다른 노드로 가는 최단거리를 구하는 알고리즘이다.

내가 기존에 알던 방식은

배열에 각각의 최단거리 갱신 -> 배열에서 최솟값 찾기 -> 그 최솟값을 기준으로 다시 탐색하기 였는데

여기서 가르친 방법은 배열에서 최솟값 찾는 과정의 효율성을 증가시키기 위해서 우선순위큐를 썼다.

파이썬 코드로 되어있어서 처음에는 이해가 잘 되지 않았지만, 지피티의 도움을 받아 자바로 이해해보았다

(확실히 파이썬이 간단하긴 하다.. 옮기고싶지만 가면 돌아올 수 없을것 같아 망설여진다ㅎㅎ)

 

이러한 노드와 간선들이 주어진다.

 

그 다음 시작 노드인 5를 기준으로 각 노드까지 가는데 얼마나 드는지를 나타내는 dist배열을 생성한다.

시작노드인 5를 기준으로는 노드5까지 가는데 비용이 들지 않으니 0으로 설정하고 나머지는 무한대(maxInt)값으로 설정한다

 

현재 저 배열 내에서 dist 값이 가장 작은 것은 5이므로, 5를 기준으로 나머지 노드 값을 갱신한다.

5에서 2로 가는데 비용 4가 들고, 이 4는 inf값보다 작으니 해당 값을 갱신시킨다.

마찬가지로 4에 해당하는 노드도 업데이트 한다.

 

위와같이 업데이트 된 배열에서 노드 4의 값이 가장 작으니까 다시 노드 4를 기준으로 배열을 갱신한다.

 

그 결과 이렇게 갱신되었다.

원래 노드 2까지 바로 가는 비용은 4였지만, 노드 4를 거쳐가는 비용과 비교했을 때 후자의 방법의 비용이 더 작으므로 갱신한다.

 

이러한 방식으로 계속 진행하여 나오는 배열이 우리가 원했던 노드 5로부터 특정 노드까지 가는 비용이다

 

코드설명

노드 생성

우선 다익스트라에서는 시작 노드에서 특정 노드까지 걸리는 비용을 저장하기 위해 노드라는 클래스가 필요하다

static class Node implements Comparable<Node> {
        int index, distance; // 노드 번호, 해당 노드까지의 거리

        public Node(int index, int distance) {
            this.index = index;
            this.distance = distance;
        }

        // 우선순위 큐에서 사용할 비교 메서드 (거리 기준 오름차순 정렬)
        @Override
        public int compareTo(Node other) {
            return Integer.compare(this.distance, other.distance);
        }
    }

index는 기준 노드에서 어떤 노드로 가는지를 나타내기 위한 필드이고

distance는 기준 노드에서 index 노드까지의 비용을 나타낸다.

 

뒤에서 다음에 탐색할 가장 비용이 작은 노드를 탐색하기 위해서 우선순위 큐를 쓴다.

이 때 노드간의 비교에서 distance를 비교하도록 하기 위해서 Comparable 인터페이스를 구현하고 compareTo 메서드를 오버라이드한다.

 

오름차순 정렬을 할 예정이기 때문에, 해당 노드의 distance 에서 들어온 파라미터의 노드의 distance를 빼서 반환하도록 하였다.

 

간선정보 저장

 public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int V = sc.nextInt();  // 노드 개수
        int E = sc.nextInt();  // 간선 개수
        int start = sc.nextInt();  // 시작 노드

        graph = new ArrayList<>(); // 그래프 초기화
        dist = new int[V + 1]; // 1-based index를 사용하기 위해 (0번 노드는 사용 X)

        // 그래프 초기화
        for (int i = 0; i <= V; i++) {
            graph.add(new ArrayList<>()); // 각 노드마다 리스트 생성
            dist[i] = INF; // 모든 노드의 초기 거리를 무한대로 설정
        }

        // 간선 정보 입력 받기
        for (int i = 0; i < E; i++) {
            int u = sc.nextInt();  // 출발 노드
            int v = sc.nextInt();  // 도착 노드
            int w = sc.nextInt();  // 가중치
            graph.get(u).add(new Node(v, w)); // 방향 그래프이므로 한쪽만 저장
        }

우선 노드와 간선의 갯수, 시작노드를 입력받고, graph에 노드의 수만큼 arrayList를 만든다 이때 0번 인덱스는 사용하지 않으므로 0부터 시작하되, v까지 모두 만들도록 해야한다.

dist는 모두 무한대로 설정한다.

 

그 다음 간선정보를 입력받는다. u번 arrayList에 v까지 w만큼 든다는 것을 표현하기 위한 노드는 집어넣는다.

이렇게 하면 u번에서 출발하는 간선들을 모두 보려면

graph.get(u)해서 나온 리스트의 사이즈만큼 해당 리스트를 순회하면 된다.

 

최소비용탐색

public static void dijkstra(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>(); // 우선순위 큐 (최소 힙)
        pq.offer(new Node(start, 0)); // 시작 노드를 큐에 삽입 (거리 0)
        dist[start] = 0; // 시작 노드의 최단 거리는 0

        while (!pq.isEmpty()) { // 큐가 비어있을 때까지 반복
            Node now = pq.poll(); // 현재 방문할 노드 가져오기 (가장 작은 거리)
            int curNode = now.index;  // 현재 노드 번호
            int curDist = now.distance; // 현재까지의 거리

            // 이미 처리된 노드라면 무시 (더 짧은 경로가 존재하는 경우)
            if (curDist > dist[curNode]) continue;

            // 현재 노드에서 이동할 수 있는 모든 노드 탐색
            for (Node next : graph.get(curNode)) {
                int cost = dist[curNode] + next.distance; // 현재 노드를 거쳐가는 비용 계산

                // 더 짧은 경로를 발견하면 갱신
                if (cost < dist[next.index]) {
                    dist[next.index] = cost; // 최단 거리 갱신
                    pq.offer(new Node(next.index, cost)); // 갱신된 노드를 큐에 삽입
                }
            }
        }
    }

본격적으로 다익스트라 알고리즘을 구현하는 코드이다.

Node를 수용하는 우선순위큐를 만들고, 시작노드를 여기에 삽입한다.

 

그 다음 큐가 빌때까지 큐에서 노드를 꺼낸다

만약 해당 노드의 curDist 값이 dist[curNode]보다 크다면, 이미 갱신된 값보다도 크다는 뜻이므로, 그 노드는 이미 조회를 했음을 뜻한다. 따라서 이런 경우 continue를 통해서 노드를 버린다

 

만약 아니라면 해당 노드를 처음 순회하는 것이므로, 그 노드에서 이동할 수 있는 모든 노드를 탐색하고, 만약 출발노드에서 현재 노드까지의 거리 + 현재 노드에서 도착노드까지의 거리값이  현재 dist값보다 작으면 도착노드의 dist 값을 갱신하고, 도착노드와 이 값으로 노드 객체를 만들어 우선순위큐에 넣는다.

 

이 과정을 반복하다가 코드가 끝이 나면 dist에 있는 값들이 출발노드에서 각 노드까지의 최소비용이 된다.

 

출처

https://www.codetree.ai/trails/complete/curated-cards/intro-ga-dijkstra/introduction

Code Tree | Learning to Code with Confidence