A Shortest Path Search Algorithm using a Method of Level Target Search
Abstract
차량용 내비게이션에는 일반적으로 Dijkstra 알고리즘(DA)이 적용되고 있다. DA는 출발 지점 s에서 특정 목표지점 t까지 최단경로로 도달하기 위해 전체 n개 정점 모두에 대한 최단거리를 결정하기 위해 m개 간선 각각의 경로 길이를 모두 계산하여야 한다. 이 논문은 1차적으로 출발 정점부터 목적지 정점까지 레벨을 설정하고 역-레벨 간선을 삭제하여 출발 정점에서 목적지 정점 방향 간선들만 선택하여 망을 축소 시켰다. 다음으로 모든 정점들의 유출 최소 가중치 간선을 2개씩 선택하고, 선택된 간선들 중 최단 경로에 기여하지 못하는 간선들을 3단계에 걸쳐 제거하여 망을 2차로 축소 시켰다. 마지막으로, 단순화된 망의 간선들만을 대상으로 출발 정점에서 목적지 정점으로 최단 길이를 갖는 경로를 선택하였다. 제안된 알고리즘을 8개의 양방향 또는 양방향과 단방향이 혼재된 8~30개 정점 망에 적용한 결과 모든 망에서 최단경로를 빠르면서도 쉽고 정확하게 탐색할 수 있음을 보였다.
Fields of Study & Subjects
Complexity and Algorithms in Graphs
Graph Theory and Algorithms
Robotic Path Planning Algorithms
Publication details
- Journal / source
- The Journal of Korean Institute of Information Technology
- Volume
- 24
- Issue
- 1
- Pages
- 181–189
- Publication date
- 31 January 2026
- Language
- EN