[최단 경로 알고리즘] 다익스트라(dijkstra) 최단 경로 알고리즘

최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미한다.

다양한 문제 상황

 - 한 지점에서 다른 한 지점까지의 최단 경로

 - 한 지점에서 다른 모든 지점까지의 최단 경로

 - 모든 지점에서 다른 모든 지점까지의 최단 경로

각 지점은 그래프에서 노드로 표현

지점 간 연결된 도로는 그래프에서 간선으로 표현

 

다양한 문제 상황 중 한 지점에서 다른 모든 지점까지의 최단 경로를 계산하는 상황은 다익스트라 최단 경로 알고리즘을 적용하여 해결할 수 있다.

 

다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작한다.

 - 현실 세계의 도로(간선)은 음의 간선으로 표현되지 않기 때문에 이러한 상황에 다익스트라 알고리즘을 적용해 볼 수 있다.

다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류된다.

 - 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복한다.

 

동작 과정

1. 출발 노드를 설정

2. 최단 거리 테이블을 초기화

 - 자기 자신을 제외한 모든 노드까지의 거리를 무한으로, 자기 자신은 0(자기 자신에서 자기 자신으로 가는 최소 비용)으로 설정

3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택 => 그리디

4. 선택한 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신

3, 4번 과정을 반복(모든 노드가 방문처리 될 때까지)

 

3번 과정에서 그리디 알고리즘으로 문제를 해결할 수 있었던 이유?

방문하지 않은 노드중 최단 거리가 가장 짧은 노드를 선택했기에, 선택된 노드까지의 최단 거리는 더 이상 바뀌지 않아서

즉, 매번 현재를 기준으로 하여 최단 거리가 가장 짧은 노드를 선택하는 과정을 반복할 때마다, 특정 노드까지의 최단거리를 확실히 결정한다고 볼 수 있다.

 

위 과정을 통해 우리가 얻을 수 있는 것은 출발 노드에서 다른 노드들까지의 최단 거리이다.

 

최단 경로를 알고 싶다면 별도의 로직이 사용되어야 한다. => (추후 학습)

 

알고리즘 동작과정에서 최단 거리 테이블은 각 노드에 대한 현재까지의 최단 거리 정보를 가지고 있다.

처리 과정에서 더 짧은 경로를 찾으면 이를 최단 거리로 다시 업데이트한다.

예를 들어, 출발노드에서 A 노드까지의 최단 경로를 처음에 8로 계산하여 최단 거리 테이블에 저장했다고 하자.

이후 출발노드에서 B(방문하지 않은 노드)를 선택하고

(출발노드에서 B까지의 거리는 5) + (B 노드에서 A노드 까지 거리 5)라면  출발노드에서 노드 B를 거처 A노드로 가는 경로의 길이(7)가

이전에 갱신했던 8보다 짧으므로, 출발 노드에서 A 노드까지의 최단 경로를 최단 거리 테이블에서 7로 업데이트한다.

 

 

예시)

출발 : 1번 노드

노드 번호	1	2	3	4	5	6
거리	0	무한	무한	무한	무한	무한

 

Step 1) 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드인 1번 노드 선택

1번 노드를 거쳐서 갈 수 있는 2,3,4 노드에 대해서 =>시작 지점이 1번이므로 1번 노드에서 1번노드를 거쳐 2,3,4 노드로 간다는 것

시작노드(1번)에서 2,3,4번 노드로 갈 수 있는 최단 거리 vs 시작 노드에서 1번 노드까지 거리 0 + 1번노드 거처 2,3,4 노드로 가는 거리 

인접 노드	현재값	거처갈 경우	갱신 여부
2	무한	0 + 2	True
3	무한	0 + 5	True
4	무한	0 + 1	True

지금은 현재 값이 모두 무한이므로 시작노드에서 1번노드를 거처 2,3,4번 노드로 가는 경우가 더 짧으므로 최단 경로 테이블을 갱신한다.

노드 번호	1	2	3	4	5	6
거리	0	2	5	1	무한	무한

 

한번 처리한 1번 노드는 더 이상 선택 x (방문 처리) => 여기선 회색으로 표현

Step 2) 아직 방문처리 되지 않은 노드 중에서 최단 거리가 가장 짧은 4번 노드 선택

4번 노드를 거쳐서 갈 수 있는 3, 5번 노드에 대해서 거리 비교

현재 시작노드(1번)에서 3, 5번 노드로 갈 수 있는 최단 거리 vs 시작 노드에서 4번 노드까지 거리 + 4번노드 거처 3,5번 노드로 가는 거리 

인접 노드	현재값	거처갈 경우	갱신 여부
3	5	1 + 3	True
5	무한	1 + 1	True

4 번 노드를 거처가는 경우가 현재 최단 거리 테이블에 저장된 값들 보다 작으므로 두 노드 모두 갱신

노드 번호	1(visited)	2	3	4	5	6
거리	0	2	4	1	2	무한

 

4번 노드 방문 처리

step 3) 아직 방문처리 되지 않은 노드 중, 최단 거리가 가장 짧은 2번 노드 선택 (2, 5번 노드 둘다 거리가 2이기 때문에 번호 작은 2 선택)

2번 노드를 거쳐서 갈 수 있는 3, 4번 노드에 대해서 거리 비교 (4번 노드는 이미 방문 처리된 노드이므로 Skip 가능)

현재 시작노드(1번)에서 3, 4번 노드로 갈 수 있는 최단 거리 vs 시작 노드에서 2번 노드까지 거리 + 2번노드 거처 3,4번 노드로 가는 거리 

인접 노드	현재값	거처갈 경우	갱신 여부
3	4	2 + 3	False
4	1	2 + 2	False

두 경우 모두 현재 상태가 더 작으므로 최단 거리 테이블 갱신하지 않음

노드 번호	1(visited)	2	3	4(visited)	5	6
거리	0	2	4	1	2	무한

 

2번 노드 방문 처리

step 4) 아직 방문처리 되지 않은 노드 중, 최단 거리가 가장 짧은 5번 노드 선택

5번 노드를 거쳐서 갈 수 있는 3, 6번 노드에 대해서 거리 비교 

현재 시작노드(1번)에서 3, 6번 노드로 갈 수 있는 최단 거리 vs 시작 노드에서 5번 노드까지 거리 + 5번노드 거처 3,6번 노드로 가는 거리 

인접 노드	현재값	거처갈 경우	갱신 여부
3	4	2 + 1	True
6	1	2 + 2	True

두 경우 모두 현재값보다 5번 노드를 거쳐갈 경우가 짧으므로 최단 거리 테이블 갱신

노드 번호	1(visited)	2(visited)	3	4(visited)	5	6
거리	0	2	3	1	2	4

 

5번 노드 방문처리

step 5) 아직 방문처리 되지 않은 노드 중, 최단 거리가 가장 짧은 3번 노드 선택

3번 노드를 거쳐서 갈 수 있는 2, 6번 노드에 대해서 거리 비교 (2번 노드는 방문처리가 되었으므로 Skip 가능)

현재 시작노드(1번)에서 2, 6번 노드로 갈 수 있는 최단 거리 vs 시작 노드에서 3번 노드까지 거리 + 3번노드 거처 2,6번 노드로 가는 거리 

인접 노드	현재값	거처갈 경우	갱신 여부
2	2	3 + 3	False
6	4	3 + 5	False

두 경우 모두 현재 상태가 더 작으므로 최단 거리 테이블 갱신하지 않음

노드 번호	1(visited)	2(visited)	3	4(visited)	5(visited)	6
거리	0	2	3	1	2	4

 

step 6) 아직 방문처리 되지 않은 노드 중, 최단 거리가 가장 짧은 6번 노드 선택 => 사실상 마지막 노드이므로 Skip 해도 됨

이미 나머지 노드들에 대한 최단 경로가 방문처리되면서 최단 거리로 고정되었기 때문이다.

6번을 거처 갈 노드가 없는 경우이므로 갱신할 노드가 존재하지 않기도 하다.(인접 노드 있어도 이미 방문처리 된 노드들이므로 갱신 안됨)

노드 번호	1(visited)	2(visited)	3(visited)	4(visited)	5(visited)	6
거리	0	2	3	1	2	4

 

이렇게 최단 거리 테이블이 완성 되었다면 우리는 이 테이블을 통해 시작 노드(1번)으로 부터 다른 모든 노드들까지의 각각의 최단 경로를 구한 것이 된다. 

 

 

다익스트라 알고리즘 정리

그리디 알고리즘 : 매 상황에서 방문하지 않은 가장 비용이 적은 노드를 선택해 임의의 과정을 반복한다.

단계를 거치며 한 번 처리된 노드의 최단 거리는 고정되어 더 이상 바뀌지 않는다.

 - 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는 것으로 이해할 수 있다.

다익스트라 알고리즘을 수행한 뒤에 테이블에 각 노드까지의 최단 거리 정보가 저장된다.

 - 완벽한 형태의 최단 경로를 구하려면 추가적 기능이 필요

 

 

구현에 필요한 요소 및 구현

private static final int INF = Integer.MAX_VALUE; //

int N; // 노드의 개수

int[][] graph;   // 각 노드에 연결되어 있는 노드에 대한 정보를 담는 2차원 배열

bool[] vsitied; // 방문한 노드인지 체크하는 배열 

 

int[] d;             // 최단 거리 테이블

 

// n개의 노드를 가진 그래프 생성
public Dijkstra(int n) {
    this.N = n;
    this.graph = new int[N][N];
    this.visited = new boolean[N];
    this.distance = new int[N];

    // 그래프 초기화
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (i == j) {
                graph[i][j] = 0;  // 자기 자신으로의 거리는 0
            } else {
                graph[i][j] = INF;  // 다른 모든 노드로의 거리는 무한대로 초기화
            }
        }
    }
}

// 방문하지 않은 노드 중 가장 최단 거리가 짧은 노드의 번호를 반환
private int getSmallestNode() {
    int min = INF;
    int index = 0;

    for (int i = 0; i < N; i++) {
        if (!visited[i] && distance[i] < min) {
            min = distance[i];
            index = i;
        }
    }
    return index;
}

 

// 다익스트라 알고리즘을 수행하는 메소드
public void dijkstra(int start) {
    // 최단 거리 테이블 초기화
    for (int i = 0; i < N; i++) {
        distance[i] = graph[start][i];
    }

    // 시작 노드 방문 처리
    visited[start] = true;

    // 시작 노드를 제외한 N-1개의 노드에 대해 반복
    for (int i = 0; i < N - 1; i++) {
        // 현재 최단 거리가 가장 짧은 노드를 꺼내서 방문 처리
        int current = getSmallestNode();
        visited[current] = true;

        // 현재 노드와 연결된 다른 노드들을 확인
        for (int j = 0; j < N; j++) {
            if (!visited[j]) {
                // 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우 갱신
                if (graph[current][j] != INF &&
                        distance[current] + graph[current][j] < distance[j]) {
                    distance[j] = distance[current] + graph[current][j];
                }
            }
        }
    }
}

 

 

성능

V : 노드의 개수 

총 O(V)번에 걸쳐서 최단 거리가 가장 짧은 노드를 매번 선형 탐색해야 한다.

따라서 전체 시간 복잡도는 O(V^2)이다.

 

Java에서 1초 동안 안전하게 수행할 수 있는 연산 횟수는 대략 5 * 10^7이라 한다.

O(v^2) 복잡도의 알고리즘에서, 연산 횟수는 v^2에 비례하기 때문에
v^2 ≤ 5 * 10^7
v ≤7071.07xx
결론
Java에서 O(v^2) 복잡도의 코드를 1초 안에 안전하게 실행하려면, v의 최대값은 대략 7000이다.

 

V(전체 노드의 개수)가 5000 이하라면 해당 코드로 문제를 해결할 수 있을 것이다.

 

그러나 10000개를 넘어가는 문제일 경우 10000² = 100,000,000 (1억) 연산 요구 => 시간 초과 발생 

=> 이 경우 우선순위 큐 사용을 고려해보자.

 

우선순위 큐(Priority Queue) : 우선순위가 가장 높은 데이터를 가장 먼저 삭제

스택(Stack) : 가장 나중에 삽입된 데이터 가정 먼저 삭제

큐(Queue) : 가장 먼저 삽입된 데이터 가장 먼저 삭제

 

Java PriorityQueue의 주요 시간복잡도

1. 삽입(offer/add): O(log N)
2. 삭제(poll/remove): O(log N)
3. 최솟값/최댓값 확인(peek): O(1)

우선 순위 큐 사용한 최적화된 다익스트라 최단경로 알고리즘 구현

private static final int INF = Integer.MAX_VALUE;
private int N;  // 노드 개수
private List<List<Node>> graph;  // 인접 리스트로 그래프 표현
private int[] distance;  // 최단 거리 배열

• 2차원 배열 → 인접 리스트(List<List<Node>>)
• 공간복잡도: O(V²) → O(V + E)
• 실제 존재하는 간선만 저장하므로 메모리 효율적

private static final int INF = Integer.MAX_VALUE;
private int N;  // 노드 개수
private List<List<Node>> graph;  // 인접 리스트로 그래프 표현
private int[] distance;  // 최단 거리 배열

// 노드 클래스 정의
private static class Node implements Comparable<Node> {
    int index;
    int distance;

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

    @Override
    public int compareTo(Node other) { // 다른 Node 객체와 비교
        return Integer.compare(this.distance, other.distance); // 거리를 기준으로 비교
    }
    // - 음수(-1): this.distance < other.distance
    // - 0: this.distance == other.distance
    // - 양수(1): this.distance > other.distance
}

compareTo 메서드 : 우선순위 큐(PriorityQueue)에서 노드들의 순서를 정하는 데 사용

우선순위 큐는 이 compareTo 메서드를 사용하여 자동으로 거리가 짧은 노드를 먼저 반환

O(V²)에서 O(E log V)로 시간복잡도 개선

public OptimizedDijkstra(int n) {
    this.N = n;
    this.distance = new int[N];

    // 인접 리스트 초기화
    this.graph = new ArrayList<>();
    for (int i = 0; i < N; i++) {
        graph.add(new ArrayList<>());
    }
}

 

// 간선 정보 추가
public void addEdge(int from, int to, int weight) {
    graph.get(from).add(new Node(to, weight));
    // 양방향 그래프인 경우 아래 줄 추가
    // graph.get(to).add(new Node(from, weight));
}

 

public void dijkstra(int start) {
    // 최단 거리 배열 초기화
    Arrays.fill(distance, INF);
    distance[start] = 0;

    // 우선순위 큐 생성
    PriorityQueue<Node> pq = new PriorityQueue<>();
    pq.offer(new Node(start, 0));

    while (!pq.isEmpty()) {
        Node current = pq.poll();
        int currentIndex = current.index;
        int currentDistance = current.distance;

        // 현재 거리가 이미 저장된 거리보다 크면 스킵
        if (currentDistance > distance[currentIndex]) continue;

        // 현재 노드와 연결된 노드들 탐색
        for (Node next : graph.get(currentIndex)) {
            int cost = currentDistance + next.distance;

            // 현재 노드를 거쳐가는 거리가 더 짧은 경우 갱신
            if (cost < distance[next.index]) {
                distance[next.index] = cost;
                pq.offer(new Node(next.index, cost));
            }
        }
    }
}

 

public static void main(String[] args) {
    // 예시: 6개 노드의 그래프
    OptimizedDijkstra graph = new OptimizedDijkstra(6);

    // 간선 정보 추가
    graph.addEdge(0, 1, 4);
    graph.addEdge(0, 2, 2);
    graph.addEdge(1, 2, 1);
    graph.addEdge(1, 3, 5);
    graph.addEdge(2, 3, 8);
    graph.addEdge(2, 4, 10);
    graph.addEdge(3, 4, 2);
    graph.addEdge(3, 5, 6);
    graph.addEdge(4, 5, 3);

    // 노드 0에서 시작하는 다익스트라 알고리즘 수행
    graph.dijkstra(0);

    // 결과 출력
    graph.printResult();
}

 

참고 자료 

https://youtu.be/acqm9mM1P6o?si=pQeYbNvNx1xmg2Jw