토픽 26 / 82

최단 경로 (Shortest Path)

그래프에서 두 정점 사이의 가중치 합이 최소인 경로를 찾는 문제

목적: 최소 비용 경로, 네비게이션, 네트워크 라우팅

특징: 가중치 조건에 따라 적용 알고리즘 상이, 단일 출발/모든 쌍 분류

분류: 단일 출발(Dijkstra, Bellman-Ford), 모든 쌍(Floyd-Warshall)

주요 알고리즘: Dijkstra(양수 가중치), Bellman-Ford(음수 가능), Floyd-Warshall(모든 쌍)

최단 경로 알고리즘 상세 비교

적용사례: GPS 내비게이션, 네트워크 라우팅, 게임 AI, 물류

연관: Dijkstra, Bellman-Ford, Floyd-Warshall, 그래프