Rust BinaryHeap 기반 O((V+E) log V) 최단 경로 CLI 구현

A Shortest-Path CLI in Rust — Making a Min-Heap from a Max-Heap, Path Reconstruction, and Rejecting Negative Weights

SEN LLC2026년 6월 24일5분intermediate

AI 요약

Context

가중치 그래프에서 최단 경로를 탐색하는 Dijkstra 알고리즘을 Rust로 구현하며 표준 라이브러리 제약 사항 해결 필요. 특히 Rust의 BinaryHeap이 Max-Heap으로 설계되어 Min-Priority Queue가 필요한 알고리즘 특성과 충돌하는 구조적 한계 존재.

Technical Solution

State 구조체에 Ord 트레이트를 구현하여 비교 연산 순서를 반전시킨 Min-Heap 논리 구조 설계
거리 값 동일 시 인덱스(idx)까지 비교하도록 설정하여 실행 시마다 동일한 경로를 보장하는 Deterministic Path Reconstruction 구현
BinaryHeap의 decrease-key 부재를 해결하기 위해 중복 노드를 허용하고 pop 시 거리 값을 검증하여 폐기하는 Lazy Deletion 전략 채택
각 노드 갱신 시 이전 노드를 기록하는 Predecessor Map을 구축하여 대상 노드부터 역추적하는 경로 복원 로직 설계
음수 가중치 입력 시 알고리즘 불변성 붕괴를 방지하기 위해 Parse 단계에서 즉시 에러를 반환하는 Validation 계층 추가

실천 포인트

- Rust BinaryHeap 사용 시 Min-Heap이 필요하다면 Ord 트레이트의 비교 대상 순서를 반전시켜 구현할 것 - 우선순위 큐의 요소 갱신이 필요할 때 decrease-key 구현 비용 대신 Lazy Deletion을 통한 시간 복잡도 O((V+E) log V) 유지 검토 - 알고리즘 결과의 일관성을 위해 Tie-break 조건(예: 인덱스 비교)을 명시하여 결정론적 결과 보장

태그

#Rust #Dijkstra #BinaryHeap #Lazy Deletion #Time Complexity

원문 읽기