[알고리즘] 최단 경로(Shortest Path) 알고리즘

최단 경로 알고리즘이란?

최단 경로 알고리즘 특징

• 그래프 기반: 정점(Vertex)과 간선(Edge)으로 표현되는 구조에서 사용

• 가중치 고려: 간선마다 가중치(거리, 비용, 시간 등)가 존재

• 다양한 조건 최적화: 최소 거리, 최소 비용, 최소 시간 등을 찾음

• 응용 분야가 넓음: 네트워크 라우팅, 교통 경로 탐색, 물류 최적화 등

최단 경로 알고리즘 실제 적용 사례

• 네비게이션 서비스: 지도 앱의 길찾기 (카카오맵, 구글 지도)

• 통신 네트워크 라우팅: 데이터 전송 시 최적 경로 선택

• 물류/배달 경로 최적화

• 게임 AI: 캐릭터 이동 경로 탐색

주요 최단 경로 알고리즘 종류

최단 경로 알고리즘의 단계

최단 경로 알고리즘 구현 (ex. python)

import heapq

def dijkstra(graph, start):
    # graph: {노드: [(비용, 연결노드), ...]}
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    queue = [(0, start)]  # (거리, 노드)
    
    while queue:
        current_dist, current_node = heapq.heappop(queue)
        
        if current_dist > distances[current_node]:
            continue
        
        for next_dist, next_node in graph[current_node]:
            distance = current_dist + next_dist
            if distance < distances[next_node]:
                distances[next_node] = distance
                heapq.heappush(queue, (distance, next_node))
    
    return distances