Graph Constraint 분석을 통한 최적 Shortest Path 알고리즘 결정 전략

Context

문제 환경의 Weight 존재 여부와 Negative Edge 포함 여부에 따라 알고리즘의 시간 및 공간 복잡도가 크게 변동함. 단일 알고리즘 맹신 시 불필요한 연산 오버헤드 발생 및 Negative Cycle 상황에서의 무한 루프 위험 존재.

Technical Solution

• Uniform Cost 환경에서 탐색 횟수 최소화를 위한 BFS 기반 최단 경로 설계
• Positive Weight 환경에서 Priority Queue를 통한 Greedy 방식의 Dijkstra 적용으로 탐색 범위 최적화
• Negative Weight 및 Cycle 감지가 필요한 경우 Edge Relaxation 기반의 Bellman-Ford 도입
• All-Pairs Shortest Path 요구사항 충족을 위한 Triple Nested Loop 구조의 Floyd-Warshall 채택
• 구현 복잡도 감소가 우선인 상황에서 Bellman-Ford의 반복적 Relaxation을 활용한 Brute Force 접근법 적용