최단경로 문제

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

✅특정 노드로부터 각각의 다른 모든 노드로 가는 최단 경로를 모두 계산함
✅현실세계에선 음수의 간선이 없으므로 현실세계에 적용 가능한 알고리즘
✅최단경로 문제는 기본적으로 다이나믹 프로그램 알고리즘으로 분류된다. A에서 C로의 최단경로를 구할 때 B를 거치는 경로가 존재한다면 A-B의 최단경로, B-C의 최단경로가 모두 고려되는 것이기 때문이다. 다만 다익스트라 최단경로 알고리즘은 그리디 알고리즘으로 분류되기도 한다.

다익스트라 최단 경로 알고리즘 동작 과정
✅최단거리 테이블의 각 요소는 해당 번째 노드까지의 최단거리를 기록(지속갱신)
✅최단거리 테이블 초기화 시, 출발노드인 자기 자신은 0 (자기자신에서 자기자신으로 가는 비용은 0이므로), 나머지는 무한
✅3번의 이유로 그리디 알고리즘이라 볼 수 있음
=> 선택 된 노드까지의 최단거리는 바뀌지 않고 선택 순간에 확정되기 때문에 그리디 알고리즘 가능
다익스트라 최단 경로 알고리즘 특징✅ 완벽한 형태의 최단 "경로"

간단한 구현 방법

단계마다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하기 위해 매 단계마다 1차원 테이블의 모든 원소를 확인(순차 탐색)한다.

동작 원리

✅ 4번노드까지의 최단거리는 1로 고정되어 바뀌지 않음 => 그리디 가능
✅ 인접노드가 3번일 때 1(4번노드까지의 최단거리)+3(4번노드->3번노드 비용)
✅ 방문하지 않은 노드중에서 최단 거리가 가장 짧은 노드는 2, 5번 노드이지만 편의상 둘 중 작은인덱스부터 선택✅ 인접 노드 중에서 이미 방문한 4번 노드에 대해서는 값이 확정 되었기때문에 계산하지 않아도 된다. (이미 방문 처리된 인접노드는 무시)✅ 이동 가능한 인접노드가 없기도 하지만, 있더라도 이미 다른 모든 노드가 방문되었기때문에 마지막 노드는 무시한다.

소스

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>>();
    // 방문한 적이 있는지 체크하는 목적의 배열 만들기, 기본값 false
    public static boolean[] visited = new boolean[100001];
    // 최단 거리 테이블 만들기
    public static int[] d = new int[100001];
    
    //-> graph, visited, d는 0번 인덱스는 사용하지 않음

    // 방문하지 않은 노드 중에서, 가장 최단 거리가 짧은 노드의 번호를 반환
    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]);
            }
        }
    }
}

✅ 상단 그래프 기준 입력예시
6 -> n
11 -> m
1 -> start
-------> 간선(m) 11개 정보
1 2 2
1 3 5
1 4 1
2 4 2
2 3 3
3 2 3
3 6 5
4 3 3
4 5 1
5 3 1
5 6 2

성능 분석

✅ V는 노드의 개수
✅ 선형탐색 O(V) -> getSmallestNode()
✅ N-1(=>dijkstra()) * N(=>getSmallestNode) = O(N^2)
✅ 전체 노드의 개수가 5000개 이하~ : python 기준

개선된 구현 방법

우선순위 큐

힙

✅ 최소 힙 : 값이 낮은 데이터부터 추출(삭제)
✅ 힙은 삽입, 삭제 시 O(logN)만큼의 시간복잡도를 가짐 -> 다양한 알고리즘에서 사용
✅ 리스트로 우선순위 큐 구현한다면

• 삽입 시 데이터를 맨 뒤에 추가하면 되므로 상수시간 O(1) 소요
• 삭제 시 전체 데이터를 순회하며 가장 높은 우선순위 데이터를 찾기 때문에 선형시간 O(N) 소요

✅ 힙정렬 : 최소힙을 통해 배열의 원소들을 힙에 삽입/추출한 결과는 오름차순 형태 (배열의 길이가 N이라면, NlogN(삽입) + NlogN(추출) => O(NlogN))

동작 원리

✅ 갱신여부가 true인 인접 노드만 큐에 (매번 거리 순 정렬하여) 담는다 -> 특정 노드가 여러번 큐에 삽입되어도 처음에 방문처리 된 이후의 노드값은 무시된다.✅ 인접노드 4번은 이미 방문되었기때문에 최단거리가 확정되어서 갱신되지 않음✅ 3번 노드는 이미 방문처리가 되었으므로 최소값으로 확정되었다. 따라서 현재 꺼낸 원소를 무시하도록 한다 -> 방문 테이블 사용하지않고, 현재 최단거리 테이블의 3번 노드 값(3)보다 꺼낸 원소의 거리(4)가 크기때문에 꺼낸 원소를 무시한다.

소스

getSmallestNode() 및 방문테이블을 사용하지 않음

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) {
        // 삽입 시 마다 compareTo 기준으로 내부적으로 정렬된다.
        PriorityQueue<Node> pq = new PriorityQueue<>();
        // 시작 노드로 가기 위한 최단 경로는 0으로 설정하여, 큐에 삽입
        pq.offer(new Node(start, 0));
        d[start] = 0;
        while(!pq.isEmpty()) { // 큐가 비어있지 않다면
            // 가장 최단 거리가 짧은 노드에 대한 정보 꺼내기 (compareTo로 구현)
            Node node = pq.poll();
            int dist = node.getDistance(); // 현재 노드까지의 비용
            int now = node.getIndex(); // 현재 노드
            // 현재 노드가 이미 처리된 적이 있는 노드라면 무시 (방문테이블 사용 X)
            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]);
            }
        }
    }
}

✅ Comparable 인터페이스

성능 분석

✅ 반복문(while문)은 방문처리 된 노드의 경우 continue 되기 때문에 그 아래 로직(while 내의 for문)은 총 노드 개수만큼만 수행된다. 이때 while 내의 for문은 해당 노드의 인접 노드 만큼 확인하기 때문에 while 내의 for문의 총 연산 횟수는 총 간선 수 만큼이다.
✅ 중복 간선을 포함하지 않는 경우 : 두 노드 사이의 존재할 수 있는 간선은 최대 오는 간선, 가는 간선 두개
✅ 노드의 개수를 V 간선의 개수는 V^2 이하의 값일 것이다.

참고

✅ 다른 예제