다익스트라(Dijkstra) [Python][Java]

[WEEK03] 다익스트라 알고리즘

 

파이썬으로 다익스트라 알고리즘 구현하기

이미 여러 번 다익스트라에 대해 다뤘지만 까먹은 관계로 공부하는 차원에서 다시 정리해본다😅

🧩 다익스트라란?

다익스트라 알고리즘은 가중치가 있는 그래프에서 한 시작 정점으로부터 다른 모든 정점까지의 최단 거리를 구하는 알고리즘이다. 단, 모든 간선의 가중치가 0 이상이어야 한다.

핵심 아이디어

1. 시작 정점의 거리를 0, 나머지 정점의 거리를 INF로 설정한다.
2. 아직 처리하지 않은 정점 중 거리가 가장 짧은 정점을 선택한다.
3. 선택한 정점을 거쳐 다른 정점으로 가는 경로가 더 짧다면 거리를 갱신한다.
4. 우선순위 큐를 이용해 2~3번 반복한다.

예를 들어 현재 A까지의 거리가 5이고, A → B 간선의 가중치가 3이라면 새로운 B까지의 거리는 5 + 3 = 8이 된다. 기존에 알려진 B까지의 거리가 10이었다면 이를 8로 갱신한다. 이 과정을 완화(Relaxation)라고 한다.

• 잠정 거리: 현재까지 발견한 경로 중 가장 짧은 거리
• 확정 거리: 더 이상 짧아질 수 없다고 증명된 최단 거리

다익스트라 진행 과정

다익스트라는 다음 두 동작 과정을 반복한다.

1. 최단 거리가 확정되지 않은 정점 중 잠정 거리가 가장 작은 정점을 선택한다.
2. 그 정점을 경유했을 때 이웃 정점의 거리가 더 짧아지는지 확인한다. 완화

현재 정점을 u, 이웃 정점을 v, 간선의 가중치를 w라고 하면 다음 값을 비교한다.

• 현재 알려진 v까지의 거리: distance[v]
• u를 거쳐 v까지 가는 거리: distance[u] + w

만약 distance[u] + w < distance[v] 조건이 성립하면 v까지의 거리를 distance[v] = distance[u] + w로 갱신한다.

왜 가장 가까운 정점의 거리를 확정해도 되는가?

현재 확정되지 않은 정점 중 잠정 거리가 가장 작은 정점을 u라고 하자. 알고리즘은 u를 선택하면서 u의 잠정 거리를 실제 최단 거리로 확정한다.

 

여기서 아직 발견하지 못한 더 짧은 경로가 있다고 가정해 보자. 그 경로는 아직 확정되지 않은 다른 정점 v를 거쳐 u로 와야 한다. 하지만 다음과 같은 모순이 발생한다.

1. u는 확정되지 않은 정점 중 현재 거리가 가장 작다.
2. 따라서 다른 미확정 정점 v까지 가는 거리는 u의 현재 거리 이상이다.
3. v에서 u로 오는 간선의 가중치도 0 이상이다.
4. 따라서 v를 거쳐 u로 오는 경로는 u의 현재 경로보다 짧을 수 없다.

즉, u의 거리는 더 이상 줄어들 수 없다. 단, 이 논리는 간선 가중치가 음수가 없을 때만 성립하며, 음수 가중치가 존재하는 경우 다익스트라 알고리즘을 사용할 수 없고, 벨만-포드 같은 알고리즘을 사용해야 한다.

🧩 예제로 보는 다익스트라

다음과 같은 방향 그래프가 있다고 하자.

시작 정점이 A일 때, 초기 상태는 다음과 같다.

A	B	C	D	E
0	INF	INF	INF	INF

1단계: A 선택

현재 가장 가까운 정점은 A이다. A의 거리를 0으로 확정하고, A에서 나가는 간선을 확인한다.

• A → B: 0 + 4 = 4
• A → C: 0 + 2 = 2

따라서 C의 거리를 2로 갱신한다.

A	B	C	D	E
0	4	2	INF	INF

※ 붉은색은 확정 거리를 의미한다.

2단계: C 선택

확정되지 않은 정점 중 거리가 가장 작은 정점은 C다. C의 최단 거리를 2로 확정하고 C의 이웃을 확인한다.

• C → B: 2 + 1 = 3 ⇒ 기존 B의 거리는 4였으므로 3으로 갱신
• C → D: 2 + 8 = 10
• C → E: 2 + 10 = 12

A	B	C	D	E
0	3	2	10	12

3단계: B 선택

확정되지 않은 정점 중 B의 거리가 가장 작으므로 B를 선택한다.

• B → D: 3 + 5 = 8

A	B	C	D	E
0	3	2	8	12

4단계: D 선택

확정되지 않은 정점 중 D의 거리가 가장 작으므로 D를 선택한다.

• D → E: 8 + 2 = 10

A	B	C	D	E
0	3	2	8	10

5단계: E 선택

확정되지 않은 정점 중 E의 거리가 가장 작으므로 E를 선택한다. 모든 정점의 거리가 확정되었으므로 알고리즘을 종료한다.

도착 정점	최단 거리	최단 경로
A	0	A
B	3	A → C → B
C	2	A → C
D	8	A → C → B → D
E	10	A → C → B → D → E

🧩 우선순위 큐란?

우선순위 큐(Priority Queue)는 데이터를 넣은 순서가 아니라 우선순위가 높은 데이터부터 꺼내는 자료구조다.

 

일반 큐가 먼저 들어온 데이터를 먼저 꺼내는 FIFO 방식이라면, 우선순위 큐는 우선순위를 기준으로 데이터를 꺼낸다.

• 최소 우선순위 큐: 가장 작은 값을 먼저 꺼냄
• 최대 우선순위 큐: 가장 큰 값을 먼저 꺼냄

대부분 힙(Heap) 자료구조로 구현하며, 삽입과 삭제는 $O(log N)$, 최대/최소값 확인은 $O(1)$의 시간 복잡도를 가진다.

다익스트라에서 우선순위 큐를 사용하는 이유

다익스트라는 매 단계마다 아직 처리하지 않은 정점 중 거리가 가장 작은 정점을 찾아야 한다. 단순 배열에서 매번 거리의 최솟값을 찾으면 정점 전체를 반복해야 해서 $O(V^2)$의 시간 복잡도를 가질 것이다. 반면 최소 힙 기반의 우선순위 큐를 사용하면 가장 거리가 작은 정점을 효율적으로 꺼낼 수 있다.

• 삽입: $O(log V)$
• 최소값 제거: $O(log V)$

인접 리스트와 우선선위 큐를 함께 사용하면 전체 시간 복잡도는 $O((V+E)\ log V)$가 되며, 흔히 $O(E\ log V)$로 표현하기도 한다.

최소 힙 코드 예시

• Python

import heapq

queue = []

heapq.heappush(queue, (5, "A"))
heapq.heappush(queue, (2, "B"))
heapq.heappush(queue, (3, "C"))

print(heapq.heappop(queue))  # (2, 'B')

• Java

import java.util.PriorityQueue;

PriorityQueue<Integer> queue = new PriorityQueue<>();

queue.offer(5);
queue.offer(2);
queue.offer(3);

System.out.println(queue.poll()); // 2

🧩 다익스트라 코드 구현 예시

Python

import heapq

def dijkstra(n, graph, start):
    INF = float("inf")

    # distance[i] = 시작점에서 i번 정점까지의 최단 거리
    distance = [INF] * (n + 1)
    distance[start] = 0

    # (거리, 정점)
    priority_queue = [(0, start)]

    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)

        # 이미 더 짧은 경로가 발견된 경우 무시
        if current_distance > distance[current_node]:
            continue

        # 현재 정점과 연결된 간선 확인
        for next_node, weight in graph[current_node]:
            new_distance = current_distance + weight

            # 더 짧은 경로를 발견했다면 갱신
            if new_distance < distance[next_node]:
                distance[next_node] = new_distance
                heapq.heappush(
                    priority_queue,
                    (new_distance, next_node)
                )

    return distance

n = 5
graph = [[] for _ in range(n + 1)]

# graph[출발 정점].append((도착 정점, 가중치))
graph[1].append((2, 2))
graph[1].append((3, 5))
graph[2].append((3, 1))
graph[2].append((4, 2))
graph[3].append((4, 3))
graph[4].append((5, 1))

distances = dijkstra(n, graph, 1)

for node in range(1, n + 1):
    if distances[node] == float("inf"):
        print(f"{node}: 도달할 수 없음")
    else:
        print(f"{node}: {distances[node]}")
'''
1: 0
2: 2
3: 3
4: 4
5: 5
'''

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

public class DijkstraExample {

    // 그래프의 간선
    static class Edge {
        int to;
        int weight;

        Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    // 우선순위 큐에 저장할 상태
    static class State implements Comparable<State> {
        int node;
        long distance;

        State(int node, long distance) {
            this.node = node;
            this.distance = distance;
        }

        @Override
        public int compareTo(State other) {
            return Long.compare(this.distance, other.distance);
        }
    }

    static long[] dijkstra(
            int n,
            List<List<Edge>> graph,
            int start
    ) {
        long INF = Long.MAX_VALUE;
        long[] distance = new long[n + 1];
        Arrays.fill(distance, INF);

        PriorityQueue<State> priorityQueue = new PriorityQueue<>();

        distance[start] = 0;
        priorityQueue.offer(new State(start, 0));

        while (!priorityQueue.isEmpty()) {
            State current = priorityQueue.poll();

            int currentNode = current.node;
            long currentDistance = current.distance;

            // 이미 더 짧은 경로가 발견된 경우 무시
            if (currentDistance > distance[currentNode]) {
                continue;
            }

            for (Edge edge : graph.get(currentNode)) {
                int nextNode = edge.to;
                long newDistance = currentDistance + edge.weight;

                // 더 짧은 경로를 발견했다면 갱신
                if (newDistance < distance[nextNode]) {
                    distance[nextNode] = newDistance;
                    priorityQueue.offer(
                        new State(nextNode, newDistance)
                    );
                }
            }
        }

        return distance;
    }

    public static void main(String[] args) {
        int n = 5;

        List<List<Edge>> graph = new ArrayList<>();

        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        // 출발 정점 -> 도착 정점, 가중치
        graph.get(1).add(new Edge(2, 2));
        graph.get(1).add(new Edge(3, 5));
        graph.get(2).add(new Edge(3, 1));
        graph.get(2).add(new Edge(4, 2));
        graph.get(3).add(new Edge(4, 3));
        graph.get(4).add(new Edge(5, 1));

        long[] distances = dijkstra(n, graph, 1);

        for (int node = 1; node <= n; node++) {
            if (distances[node] == Long.MAX_VALUE) {
                System.out.println(node + ": 도달할 수 없음");
            } else {
                System.out.println(node + ": " + distances[node]);
            }
        }
    }
}