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

최단 경로 알고리즘

• 그래프에서 노드 간의 최소 비용 경로를 찾는 알고리즘.
• 주로 길 찾기 문제에 적용되며, 그래프의 각 지점을 노드로, 지점 간 연결된 도로를 간선으로 표현.

대표 알고리즘

• 다익스트라
• 벨만-포드
• 플로이드와샬

다익스트라

• 특징
  • 음이 아닌 가중 그래프에서 단일 출발 최단 경로 문제에 적합
  • 매 단계마다 방문하지 않은 노드 중 최단 거리 노드를 선택
• 시간 복잡도:
  • O(ElogV) (우선순위 큐 사용 시)
• 작동 원리:
  • 출발 노드 설정
  • 최단 거리 테이블 초기화
  • 방문하지 않은 노드 중 최단 거리 노드 선택
  • 해당 노드를 통한 다른 노드 경로 비용 계산
  • 최단 거리 테이블 갱신

코드

import sys
input = lambda : sys.stdin.readline().rstrip()
import heapq

def dijkstra(graph, start_node):
    # 그래프에 있는 모든 정점을 키로 하고 거리는 무한대로 초기화
    distances = {node: float('inf') for node in graph}

    # 시작 노드의 거리는 0으로 설정
    # 자기 자신까지의 거리는 항상 0이므로
    distances[start_node] = 0

    # 우선순위 큐 활용
    pq = [(0, start_node)]
    while pq:
        # 현재까지 가장 짧은 거리의 노드를 꺼냄
        # dist: 시작노드부터 현재노드까지의 거리
        # cur_node: 현재 탐색 중인 노드
        dist, cur_node = heapq.heappop(pq)

        # 이미 저장된 최단 거리보다 현재 꺼낸 거리가 더 크면 무시
        # 이는 이미 더 최적의 경로를 찾았다는 의미
        if dist > distances[cur_node]:
            continue

        # 현재 노드의 모든 인접 노드 탐색
        for neighbor, weight in graph[cur_node].items():
            # 현재 노드를 거쳐 이웃 노드로 가는 총 거리 계산
            distance = dist + weight

            # 계산된 거리가 기존에 알려진 최단 거리보다 짧으면 갱신
            # 더 짧은 경로를 찾았을 때만 distances와 우선순위 큐 업데이트
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
    # 시작 노드로부터 모든 노드까지의 최단 거리 반환
    return distances



graph = {
    'A': {'B': 7, 'C': 9},
    'B': {'A': 7, 'C': 10, 'D': 15},
    'C': {'A': 9, 'B': 10, 'D': 11, 'F': 2},
    'D': {'B': 15, 'C': 11, 'E': 6},
    'E': {'D': 6, 'F': 9},
    'F': {'C': 2, 'E': 9}
}
shortest_distances = dijkstra(graph, 'A')
print(shortest_distances)