다익스트라(Dijikstra) 알고리즘

정의

---

• 음의 가중치가 없는 그래프의 한 노드에서 각 모든 노드까지의 최단거리를 구하는 알고리즘

 

 

동작

---

• 그리디 + 동적 계획법
  1. 방문하지 않은 노드 중에서 가장 비용이 작은 노드를 선택(Greedy)
  2. 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신(DP)

 

 

초기의 Dijkstra 알고리즘

---

• 거리 테이블을 매번 탐색하는 순차 탐색 방식
• 최악의 경우 모든 노드들을 확인해야 함 → 이것을 V번 반복
• 시간복잡도 $$O(V^2)$$
• 방문 여부를 체크할 배열
• 각 노드까지의 최소 비용을 저장할 배열
  • 미 방문한 노드는 무한한 값으로 초기

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class DijkstraTable {

    static class Node {

        int idx;    // 도착 정점
        int cost;   // 도착 정점으로 가는 비용

        public Node(int idx, int cost){
            this.idx = idx;
            this.cost = cost;
        }
    }

    static final int INFINITE = Integer.MAX_VALUE;  // 무한대 값

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();

    static int V, E;    // 정점과 간선의 개수
    static int start;   // 출발 지점

    static ArrayList<Node>[] graph; // 인접 리스트
    static boolean[] visited;   // 정점 방문 여부 확인을 위한 재열
    static int[] distance;      // 출발 정점부터 도착 정점까지의 최소 거리를 저장하기 위한 배열

    public static void main(String[] args) throws IOException {

        st = new StringTokenizer(br.readLine());
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        start = Integer.parseInt(br.readLine());

        initGraph();    // 그래프 초기화

        makeGraph();    // 그래프 생성

        dijkstra();     // 다익스트라 알고리즘 실행

        printResult();  // 출발 정점에서 각 정점으로 이동 시의 최소 비용 출력

        br.close();
    }

    // 그래프 초기화
    static void initGraph(){
        graph = new ArrayList[V + 1];   // 정점의 idx는 1 ~ V + 1번까지
        for (int i = 1; i < V + 1; i++) {
            graph[i] = new ArrayList<>();
        }
    }

    static void makeGraph() throws IOException {

        // 그래프 생성
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            graph[from].add(new Node(to, cost));
        }
    }

    static void dijkstra(){

        visited = new boolean[V + 1];
        distance = new int[V + 1];

        // 최소 거리 정보를 담을 배열 초기화 -> 무한한 값으로
        Arrays.fill(distance, INFINITE);
        distance[start] = 0;    // 출발 지점은 0으로 초기화

        // 다익스트라 알고리즘
        // 모든 정점을 방문했다면 종료 (정점의 개수만큼 반복)
        for (int v = 1; v < V + 1; v++) {

            int minCost = INFINITE;
            int minIdx = -1;

            // 현재 정점에서의 거리 비용이 최소인 정점을 선택
            for (int i = 1; i < V + 1; i++) {
                if (!visited[i] && distance[i] < minCost){
                    minCost = distance[i];
                    minIdx = i;
                }
            }

            // 그래프가 끊어진 경우
            if (minIdx == -1){
                break;
            }

            // 최종적으로 선택된 정점을 방문처리
            visited[minIdx] = true;

            // 선택된 정점을 기준으로 인접한 정점의 최소 거리 값을 갱신
            for (Node node : graph[minIdx]){

                // 인접 정점이 현재 가지는 최소 비용 VS 현재 선택된 정점의 비용 + 현재 선택된 정점에서 인접 정점으로 가는 비용
                if (distance[node.idx] > distance[minIdx] + node.cost){
                    distance[node.idx] = distance[minIdx] + node.cost;
                }
            }
        }
    }

    static void printResult(){
        for (int i = 1; i < distance.length; i++) {
            sb.append(distance[i] == INFINITE ? "INF" : distance[i]).append("\\n");
        }
        System.out.println(sb);
    }
}

 

 

우선순위 큐를 이용한 Dijkstra 알고리즘

---

• 기본적인 다익스트라 알고리즘
  • 최소 비용을 갖는 노드를 선택 → 주변 노드의 값을 갱신
  • 비용을 나타내는 배열에서 갱신된 노드를 제외하고는 무한한 값을 가지게 됨
  • 그런 애들을 고려할 필요가 있을까?
• 갱신하는 주변 노드의 값에 대해서만 다음 최소 비용을 갖는 노드를 선택하면 됨
• 삽입연산
  • 우선순위 큐에 삽입하는 최대 횟수는 간선의 개수 → O(ELogE)
  • 희소 그래프(간선이 얼마 없는 그래프)의 경우 E <= V^2 → O(ElogV)
• 추출연산
  • 최대 V개의 노드에 대하여 우선순위 큐에서 추출 → O(VlogV)
  • 그러나 모든 인접 노드들을 우선순위 큐에 넣는다면 O(VlogV)를 보장하지 못함
  • 최적의 알고리즘 구현을 위해서는 중복되는 노드들을 방문하지 않도록 조건을 넣어줘야 함
• 시간복잡도 $$O((E+V)logV)$$

 

package com.ssafy.algorithm.mst;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class DijkstraPQ {

    // 우선순위 큐 사용을 위한 Comparable 인터페이스 구현
    static class Node implements Comparable<Node> {

        int idx;    // 도착 정점
        int cost;   // 도착 정점으로 가는 비용

        public Node(int idx, int cost){
            this.idx = idx;
            this.cost = cost;
        }

        @Override
        public int compareTo(Node other) {
            // 비용이 작을 수록 높은 우선순위
            return Integer.compare(this.cost, other.cost);
        }
    }

    static final int INFINITE = Integer.MAX_VALUE;  // 무한대 값

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();

    static int V, E;    // 정점과 간선의 개수
    static int start;   // 출발 지점

    static ArrayList<Node>[] graph; // 인접 리스트
    static PriorityQueue<Node> pq = new PriorityQueue<>();
    static int[] distance;      // 출발 정점부터 도착 정점까지의 최소 거리를 저장하기 위한 배열

    public static void main(String[] args) throws IOException {

        st = new StringTokenizer(br.readLine());
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());
        start = Integer.parseInt(br.readLine());

        initGraph();    // 그래프 초기화

        makeGraph();    // 그래프 생성

        dijkstra();     // 다익스트라 알고리즘 실행

        printResult();  // 출발 정점에서 각 정점으로 이동 시의 최소 비용 출력

        br.close();
    }

    // 그래프 초기화
    static void initGraph(){
        graph = new ArrayList[V + 1];   // 정점의 idx는 1 ~ V + 1번까지
        for (int i = 1; i < V + 1; i++) {
            graph[i] = new ArrayList<>();
        }
    }

    static void makeGraph() throws IOException {

        // 그래프 생성
        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            graph[from].add(new Node(to, cost));
        }
    }

    static void dijkstra(){

        distance = new int[V + 1];

        // 최소 거리 정보를 담을 배열 초기화 -> 무한한 값으로
        Arrays.fill(distance, INFINITE);
        distance[start] = 0;    // 출발 지점은 0으로 초기화

        // 시작 정점에서 시작 정점으로 가는 최소 비용은 0
        pq.offer(new Node(start, 0));

        // 다익스트라 알고리즘
        while (!pq.isEmpty()) {
            Node minNode = pq.poll();   // 우선순위 큐에서 poll한 노드 -> 현재 최소 비용을 갖는 정점

            // 해당 정점의 비용이 distance 배열에 저장된 값보다 크다면 고려할 필요없음
            // 이 코드가 있어야 중복 방문을 막을 수 있음
            if (distance[minNode.idx] < minNode.cost) {
                continue;
            }

            // 선택된 정점의 모든 인접 정점들을 탐색
            for (Node node : graph[minNode.idx]){

                // 간선으로 연결된 정점들을 모두 우선순위 큐에 넣어준다면 중복 발생
                // 인접 정점으로의 distance 값과 현재 선택된 정점에서 인접 정점으로 가는 비용을 비교
                if (distance[node.idx] > minNode.cost + node.cost){
                    distance[node.idx] = minNode.cost + node.cost;
                    pq.offer(new Node(node.idx, distance[node.idx]));
                }
            }
        }
    }

    static void printResult(){
        for (int i = 1; i < distance.length; i++) {
            sb.append(distance[i] == INFINITE ? "INF" : distance[i]).append("\\n");
        }
        System.out.println(sb);
    }
}

 

 

참고자료

---

• https://sskl660.tistory.com/59
• https://han-joon-hyeok.github.io/posts/dijkstra-algorithm/