닥익스트라 최단경로 알고리즘

다익스트라 알고리즘

'단계마다 방문하지 않은 노드 중에서 가장 최단 거리가 짧은 노드를 선택'한 뒤에, 그 노드를 거쳐 가는 경우를 확인하여 최단 거리를 갱신하는 방법이다. 우선순위 큐를 이용하여 풀 수 있다.

 

<풀이 방법>

1. 문제가 주로 한 정점에서 다른 정점까지 가는 최단거리를 계산하는 게 주로 나온다.

2. Java의 경우 class Node를 만들어서 정점과 간선을 표현하자.

    // PriorityQueue 사용을 위해 Comparable 사용함
    class Node implements Comparable<Node> {
        int v; // 정점
        int c; // 이동값
        Node (int v, int c) {
            this.v = v;
            this.c = c;
        }

        @Override
        public int compareTo(Node o) {
            return this.c - o.c; // 이동값 기준으로 오름차순
        }
    }

 

3. 인접리스트 배열로 입력값을 정리한다.

    void InputData() {
        Scanner in = new Scanner(System.in);
        V = in.nextInt();
        E = in.nextInt();
        K = in.nextInt();
        list = new ArrayList[V+1]; // 정점은 보통 1 ~ N까지니까 N+1만큼 배열 생성
        for (int i=1; i<=V; i++) {
            list[i] = new ArrayList<Node>(); // 정점의 수만큼 ArrayList<Node>를 먼저 할당한다.
        }
        
        for (int i=0; i<E; i++) {
            int s = in.nextInt(); // 시작정점
            int e = in.nextInt(); // 도착정점
            int cost = in.nextInt(); // 간선의 가중치
            list[s].add(new Node(e, cost)); // 방향이 있는 노드
            //list[e].add(new Node(s, cost)); // 방향이 없는 노드는 역순으로 한번더 입력
        }
    }

 

4. int distance[] 배열을 정의해서 이동거리의 누적값을 최소값으로 관리한다. INF로 초기화한다.

5. 다익스트라 알고리즘 수행

  a. 초기 작업

    - PriorityQueue PQ를 정의해서 시작점을 넣는다.

    - 거리배열 시작점 초기화

  b. 탐색 시작

    - PQ가 빌 때까지 반복문 수행

    - 큐에서 node값을 받아온다.

    - 현재위치가 도착지점이면 최단거리 출력하고 종료

    - 현재 노드까지의 최단거리가 거리배열의 값보다 크면 패스 (탐색할 필요가 없음)

    - 

 

    void dijkstra(int start) {
        PriorityQueue<Node> PQ = new PriorityQueue<>();
        PQ.offer(new Node(start, 0)); // 시작점 삽입
        distance[start] = 0; // 거리배열 시작점 업데이트

        while (!PQ.isEmpty()) {
            Node now = PQ.poll();
            
            // 특정 목적지에 도착하는 문제면, 최단거리 출력 후 break
            if (now.v == N) {
                System.out.println(now.c);
                break;
            }
            
            // 더 큰 가중치로 도착한 경우 패스
            if (now.c > distance[now.v]) continue;
            
            // 현재 위치와 연결된 간선 탐색
            for (Node next : list[now.v]) {
                // 최단거리가 더 작을때만 큐에 넣도록 수정(메모리초과 개선)
                if (distance[next.v] > distance[now.v] + next.c) {
                    distance[next.v] = distance[now.v] + next.c;
                    // 현재까지 최단거리를 다음 비교를 위해 큐에 삽입.
                    PQ.offer(new Node(next.v, distance[next.v]));
                }
            }
        }
    }