알고리즘 : 최단 경로 알고리즘 (1) - 다익스트라(Dijkstra) 알고리즘 (Java로 구현)

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

최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미한다. 최단 경로 알고리즘 중 다익스트라 알고리즘은 다음과 같은 특징을 가지고 있다.

• 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산한다
• 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 사용할 수 있다
• 다익스트라 최단 경로 알고리즘은 그리디 알고리즘 중 하나이다. 매 상황에서 가장 비용이 적게 드는 노드를 선택하기 때문이다.

다음은 다익스트라 최단 경로 알고리즘의 동작 과정을 간단히 서술한 내용이다.

1. 출발 노드를 설정한다.
2. 최단 거리 테이블을 초기화한다.
   이 때, 다른 노드까지의 거리를 무한으로 설정하고 자기 자신까지의 거리는 0으로 설정한다.
3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리를 테이블 갱신한다
5. 3, 4번을 반복한다.

B를 거치면서 A까지의 최단 경로가 7이라는 것을 알고 테이블을 갱신해주게 되는 것이다.

 

 

동작과정

[초기상태] 그래프를 준비하고 출발 노드를 설정한다. 그래프를 준비하고 테이블에서 출발 노드까지의 거리를 초기화한다.

 

[1] 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드인 1번 노드를 처리한다.

 

[2] 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드인 4번을 처리한다. 4번 노드까지의 최단 거리는 확정적으로 바뀌지 않는다.

 

[3] 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드인 2번 노도를 처리한다. 이미 방문처리된 노드라면 최단거리가 결정된 것이기 때문에 4번은 굳이 확인하지 않아도 된다.

 

[4] 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드인 5번 노드를 처리한다.

 

[5] 방문하지 않은 노드 중에 최단 거리가 가장 짧은 노드인 3번 노드를 처리한다. 여기선 6번만 확인하면 된다.

 

[6] 마지막 노드는 연결된 부분이 없기 때문에 알고리즘이 마무리 된다.

 

한 번 방문된 (처리된) 노드의 처단 거리는 고정되어 더 이상 바뀌지 않는다. 완벽한 형태의 최단 경로를 구하기 위해서는 소스코드에 추가적인 기능을 넣어야 한다.

 

import java.util.*;

class Node {

    private int index;
    private int distance;

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

    public int getIndex() {
        return this.index;
    }

    public int getDistance() {
        return this.distance;
    }
}

public class Main {

    public static final int INF = (int) 1e9; // 무한을 의미하는 값으로 10억을 설정
    // 노드의 개수(N), 간선의 개수(M), 시작 노드 번호(Start)
    // 노드의 개수는 최대 100,000개라고 가정
    public static int n, m, start;
    // 각 노드에 연결되어 있는 노드에 대한 정보를 담는 배열
    public static ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
    // 방문한 적이 있는지 체크하는 목적의 배열 만들기
    public static boolean[] visited = new boolean[100001];
    // 최단 거리 테이블 만들기
    public static int[] d = new int[100001];

    // 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호를 반환
    public static int getSmallestNode() {
        int min_value = INF;
        int index = 0; // 가장 최단 거리가 짧은 노드(인덱스)
        for (int i = 1; i <= n; i++) {
            if (d[i] < min_value && !visited[i]) {
                min_value = d[i];
                index = i;
            }
        }
        return index;
    }

    public static void dijkstra(int start) {
        // 시작 노드에 대해서 초기화
        d[start] = 0;
        visited[start] = true;
        for (int j = 0; j < graph.get(start).size(); j++) {
            d[graph.get(start).get(j).getIndex()] = graph.get(start).get(j).getDistance();
        }
        // 시작 노드를 제외한 전체 n - 1개의 노드에 대해 반복
        for (int i = 0; i < n - 1; i++) {
            // 현재 최단 거리가 가장 짧은 노드를 꺼내서, 방문 처리
            int now = getSmallestNode();
            visited[now] = true;
            // 현재 노드와 연결된 다른 노드를 확인
            for (int j = 0; j < graph.get(now).size(); j++) {
                int cost = d[now] + graph.get(now).get(j).getDistance();
                // 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
                if (cost < d[graph.get(now).get(j).getIndex()]) {
                    d[graph.get(now).get(j).getIndex()] = cost;
                }
            }
        }
    }

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

        n = sc.nextInt();
        m = sc.nextInt();
        start = sc.nextInt();

        // 그래프 초기화
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<Node>());
        }

        // 모든 간선 정보를 입력받기
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            // a번 노드에서 b번 노드로 가는 비용이 c라는 의미
            graph.get(a).add(new Node(b, c));
        }

        // 최단 거리 테이블을 모두 무한으로 초기화
        Arrays.fill(d, INF);
        
        // 다익스트라 알고리즘을 수행
        dijkstra(start);

        // 모든 노드로 가기 위한 최단 거리를 출력
        for (int i = 1; i <= n; i++) {
            // 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
            if (d[i] == INF) {
                System.out.println("INFINITY");
            }
            // 도달할 수 있는 경우 거리를 출력
            else {
                System.out.println(d[i]);
            }
        }
    }
}

계속 최단이 어떤건지 확인해야하니까 전체 시간복잡도가 O(V^2)이 된다.  여기서 V는 노드의 개수이다. 노드의 개수가 10,000개를 넘어가는 상황에서 문제가 발생하기 시작한다. 여기서

 

이에 우선순위 큐를 사용하곤 한다. 

 

 

우선순위 큐를 사용한 동작과정

[초기 상태] 그래프를 준비하고 출발 노드를 설정하여 우선순위 큐에 삽입한다. 우선순위 큐는 가중치를 기준으로 정렬된다.

 

[1] 우선순위 큐에서 원소를 꺼낸다. 1번 노드는 아직 방문하지 않았으므로 처리한다. 테이블 갱신해주고 우선순위 큐에도 삽입을 해주어야 한다.

 

[2] 우선순위 큐에서 원소를 꺼낸다. 4번 노드는 아직 방문하지 않았으므로 이를 처리한다.

 

[3] 우선순위 큐에서 원소를 꺼낸다. 2번 노드는 아직 방문하지 않았으므로 이를 처리한다.

 

이런 식으로 쭉 진행하는데 방문된 노드가 꺼내지면 무시를 하고 계속 진행하면 된다.

 

import java.util.*;

class Node implements Comparable<Node> {

    private int index;
    private int distance;

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

    public int getIndex() {
        return this.index;
    }

    public int getDistance() {
        return this.distance;
    }

    // 거리(비용)가 짧은 것이 높은 우선순위를 가지도록 설정
    @Override
    public int compareTo(Node other) {
        if (this.distance < other.distance) {
            return -1;
        }
        return 1;
    }
}

public class Main {

    public static final int INF = (int) 1e9; // 무한을 의미하는 값으로 10억을 설정
    // 노드의 개수(N), 간선의 개수(M), 시작 노드 번호(Start)
    // 노드의 개수는 최대 100,000개라고 가정
    public static int n, m, start;
    // 각 노드에 연결되어 있는 노드에 대한 정보를 담는 배열
    public static ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
    // 최단 거리 테이블 만들기
    public static int[] d = new int[100001];

    public static void dijkstra(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        // 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
        pq.offer(new Node(start, 0));
        d[start] = 0;
        while(!pq.isEmpty()) { // 큐가 비어있지 않다면
            // 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기
            Node node = pq.poll();
            int dist = node.getDistance(); // 현재 노드까지의 비용 
            int now = node.getIndex(); // 현재 노드
            // 현재 노드가 이미 처리된 적이 있는 노드라면 무시
            if (d[now] < dist) continue;
            // 현재 노드와 연결된 다른 인접한 노드들을 확인
            for (int i = 0; i < graph.get(now).size(); i++) {
                int cost = d[now] + graph.get(now).get(i).getDistance();
                // 현재 노드를 거쳐서, 다른 노드로 이동하는 거리가 더 짧은 경우
                if (cost < d[graph.get(now).get(i).getIndex()]) {
                    d[graph.get(now).get(i).getIndex()] = cost;
                    pq.offer(new Node(graph.get(now).get(i).getIndex(), cost));
                }
            }
        }
    }

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

        n = sc.nextInt();
        m = sc.nextInt();
        start = sc.nextInt();

        // 그래프 초기화
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<Node>());
        }
        
        // 모든 간선 정보를 입력받기
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            // a번 노드에서 b번 노드로 가는 비용이 c라는 의미
            graph.get(a).add(new Node(b, c));
        }

        // 최단 거리 테이블을 모두 무한으로 초기화
        Arrays.fill(d, INF);
        
        // 다익스트라 알고리즘을 수행
        dijkstra(start);

        // 모든 노드로 가기 위한 최단 거리를 출력
        for (int i = 1; i <= n; i++) {
            // 도달할 수 없는 경우, 무한(INFINITY)이라고 출력
            if (d[i] == INF) {
                System.out.println("INFINITY");
            }
            // 도달할 수 있는 경우 거리를 출력
            else {
                System.out.println(d[i]);
            }
        }
    }
}

이렇게 우선순위 큐를 이용하는 다익스트라 알고리즘의 시간복잡도는 O(ElogV)이다. 여기서 E는 간선, V는 노드이다.