다익스트라 알고리즘(Dijkstra's Algorithm)

"가중치가 있는 그래프에서 특정 시작 노드로부터 모든 노드까지의 최단 경로를 찾는 알고리즘"

• 음의 가중치가 없는 그래프에서 최단 경로를 찾을 때 사용됨
• 우선순위 큐(Priority Queue)를 활용하여 효율적으로 탐색
• 네트워크 라우팅, GPS 길 찾기, 그래프 기반 문제 해결 등에 사용됨

---

다익스트라 알고리즘 동작 원리

1. 시작 노드에서 모든 노드까지의 거리를 무한(∞)으로 초기화, 단 시작 노드는 0으로 설정
2. 현재 가장 가까운 노드를 선택하여 인접 노드의 거리 갱신
3. 모든 노드를 처리할 때까지 반복

# Pseudo Code
FUNCTION Dijkstra(graph, start):
    거리 = {모든 노드를 ∞(무한대)로 초기화}
    거리[start] = 0  # 시작 노드는 0
    우선순위 큐 PQ에 (0, start) 삽입

    WHILE PQ가 비어있지 않다면:
        (현재 거리, 현재 노드) = PQ에서 최소값 꺼내기

        IF 현재 거리 > 저장된 거리 THEN CONTINUE

        FOR 모든 인접 노드 (next, weight) in graph[현재 노드]:
            새로운 거리 = 현재 거리 + weight
            IF 새로운 거리 < 저장된 거리[next]:
                거리[next] = 새로운 거리
                PQ에 (새로운 거리, next) 삽입

    RETURN 거리
    

# Full Code
import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}  # 거리 초기화
    distances[start] = 0  # 시작 노드는 거리 0
    pq = [(0, start)]  # 우선순위 큐 (힙 사용)

    while pq:
        current_distance, current_node = heapq.heappop(pq)  # 최단 거리 노드 꺼내기

        if current_distance > distances[current_node]:
            continue  # 이미 처리된 노드는 무시

        for neighbor, weight in graph[current_node]:  # 인접 노드 탐색
            distance = current_distance + weight

            if distance < distances[neighbor]:  # 최단 거리 갱신
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))  # 큐에 삽입

    return distances  # 모든 노드까지의 최단 거리 반환

# 그래프 정의 (인접 리스트)
graph = {
    1: [(2, 2), (3, 4)],
    2: [(3, 1), (4, 3)],
    3: [(4, 5)],
    4: []
}

start_node = 1
shortest_paths = dijkstra(graph, start_node)
print(shortest_paths)

---

다익스트라 알고리즘의 시간복잡도

구현 방식	시간복잡도
우선순위 큐 (Heap 사용)	O((V + E) log V)
일반 리스트 사용	O(V²)

 

✅ 우선순위 큐를 사용하면 성능이 훨씬 좋아짐

---

다익스트라 알고리즘의 장단점

장점

 

• 가중치가 양수인 그래프에서 최단 경로를 빠르게 찾을 수 있음
• 우선순위 큐를 사용하면 O((V + E) log V)으로 최적화 가능
• GPS 내비게이션, 네트워크 라우팅 등 실생활에서 많이 사용됨

단점

 

• 음의 가중치를 가진 그래프에서는 사용할 수 없음 (벨만-포드 알고리즘 사용 필요)
• 우선순위 큐를 쓰지 않으면 성능이 O(V²)로 비효율적

결론

다익스트라 알고리즘은 가중치가 있는 그래프에서 최단 경로를 찾을 때 가장 많이 쓰이며, 우선순위 큐를 활용하면 빠르게 해결할 수 있다.