06. 내비게이션의 심장: 다익스트라 (Dijkstra)

import heapq

def run_dijkstra_nav(graph, start, end):
    """
    다익스트라(Dijkstra) 알고리즘을 이용한 우선순위 큐(Priority Queue) 기반 
    최단 경로 및 비용 갱신 내비게이션 시스템
    """
    print("🛰️ [GPS 내비게이션 다익스트라 엔진 가동]")
    
    # 거리를 모두 무한대(INF)로 초기화
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0  # 출발지는 거리 0
    
    # 궤적을 역추적하기 위한 발자국 딕셔너리
    history = {node: None for node in graph}
    
    # (누적 비용, 현재 방문 도시)
    priority_queue = [(0, start)]
    
    print(f"🚩 출발지: [{start}] ➔ 목적지: [{end}]")
    print("-" * 50)
    
    while priority_queue:
        # 우선순위 큐에서 당장 가장 싼(가까운) 노드 팝업!
        current_distance, current_node = heapq.heappop(priority_queue)
        
        # 목적지에 도달했다면 스캔 종료 승리
        if current_node == end:
            print(f"🎯 [목표 스캔 완료] 노드 [{end}] 락온!")
            break
            
        # 이미 이전에 더 싼 가격으로 처리된 노드라면 패스
        if current_distance > distances[current_node]:
            continue
            
        # 가스라이팅 갱신 타임 (주변 이웃 순회)
        for neighbor, weight in graph[current_node].items():
            cost = current_distance + weight
            
            # 내가 거쳐 가는 길이 옛날에 써둔 비용보다 싸다면 업데이트!
            if cost < distances[neighbor]:
                distances[neighbor] = cost
                history[neighbor] = current_node # 발자국 남기기 (나를 거쳐옴)
                heapq.heappush(priority_queue, (cost, neighbor))
                print(f"   🔄 [비용 갱신] [{current_node}]를 거쳐 [{neighbor}]로 가는 새로운 최저가 발견! (비용: {cost})")
                
    # 역추적으로 내비게이션 최종 루트 뽑아내기
    path = []
    curr = end
    while curr is not None:
        path.append(curr)
        curr = history[curr]
    path.reverse() # 역추적이니 거꾸로 뒤집기
    
    print("-" * 50)
    print(f"✅ 최종 최소 비용: {distances[end]} 원")
    print(f"🛣️ 추천 경로(Route): {' ➔ '.join(path)}")

# 복잡한 가중치 그래프 데이터 네트워크 구축
# A->B 요금은 2, A->C 요금은 5 ...
city_network = {
    'A': {'B': 2, 'C': 5},
    'B': {'A': 2, 'C': 1, 'D': 6},
    'C': {'A': 5, 'B': 1, 'D': 3},
    'D': {'B': 6, 'C': 3}
}

# A에서 출발하여 D까지 스캔!
run_dijkstra_nav(city_network, 'A', 'D')