본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

정보과학회논문지. Journal of KIISE. 시스템 및 이론 v.29 no.11, 2002년, pp.634 - 639   피인용횟수: 1
본 등재정보는 저널의 등재정보를 참고하여 보여주는 베타서비스로 정확한 논문의 등재여부는 등재기관에 확인하시기 바랍니다.

One-to-One 최단경로 알고리즘의 성능 평가
Performance Evaluation for One-to-One Shortest Path Algorithms

심충섭   ((주)디지웨이브CC0056017  ); 김진석   (서울대학교 컴퓨터통계학과UU0000691  );
  • 초록

    최단 경로 탐색 알고리즘 (Shortest Path Algorithm)은 출발지에서 목적지에 이르는 여러 경로 중에서 가장 경제적이고 효율적인 경로를 찾는 알고리즘으로 레이블링 기법에 기초하고 있다. 레이블링 기법에는 레이블 고정(Label-Setting) 기법과 레이블 수정 (Label-Correcting) 기법이 있다. One-to-One 최단 경로 탐색 알고리즘에서 레이블 고정 기법이 빠르다고 알려져 왔으나 최근 연구에서 대용량 도로 데이터에 대한 실험을 통해 레이블 수정이 레이블 고정보다 탐색 씨간이 빠름을 보였다[1,2]. 레이블 수정 기법 중에서 가장 속도가 빠른 것은 그래프 성장 (Graph Growth) 알고리즘인데, 이 알고리즘은 One-to-All 방식을 사용하고 있으므로 One-to-One 최단 경로 탐색에는 적합하지 않다. 본 논문에서는 One-to-One 방식을 사용하는 새로운 알고리즘을 제안하였고, 실험결과 그래프 성장 알고리즘의 성능에 비해 새로 제안된 알고리즘의 성능이 30~40 향상되었음을 알 수 있었다.


    A Shortest Path Algorithm is the method to find the most efficient route among many routes from a start node to an end node. It is based on Labeling methods. In Labeling methods, there are Label-Setting method and Label-Correcting method. Label-Setting method is known as the fastest one among One-to-One shortest path algorithms. But Benjamin[1,2] shows Label-Correcting method is faster than Label-Setting method by the experiments using large road data. Since Graph Growth algorithm which is based on Label-Correcting method is made to find One-to-All shortest path, it is not suitable to find One-to-One shortest path. In this paper, we propose a new One-to-One shortest path algorithm. We show that our algorithm is faster than Graph Growth algorithm by extensive experiments.


  • 주제어

    최단경로알고리즘.  

  • 참고문헌 (10)

    1. 최기주, 'U-Turn을 포함한 가로망 표현 및 최단경로의 구현,' 대한교통학회지, vol. 13, no. 3, pp. 35-52, 1995     
    2. 노정현, 남궁성, '도시가로망에 적합한 최단경로탐색기법의 개발,' 대한국토도시계획학회지, vol. 30, no. 5, pp. 153-168, 1995 
    3. 최재원, '시변 교통량을 고려한 차량 경로계획 시스템의 구현,' 공학석사 학위논문, 서울대학교 전기공학부 대학원, 2000 
    4. U. Pape, 'Implementation and Efficiency of Moore Algorithms for the Shortest Root Problem,' Mathematical Programming, vol. 7, pp. 212-222, 1974 
    5. S. Pallottino, 'Shortest-Path Methods : Complexity, Interrelations and New Propositions,' Networks, vol. 14, pp. 257-267, 1984 
    6. 이석호역, '자료구조론,' 홍릉과학출판사, pp. 223-224, 1991 
    7. F. B. Zhan, 'Three Fastest Shortest Path Algorithms on Real Network : Data Structures and Procedures,' Journal of Geographic Information and Decision Analysis, vol. 1, no. 1, pp. 69-82, 1997 
    8. B. V. Cherkassky, A. V. Goldberg and T. Redzik, 'Shortest Paths Algorithms : Theory and Experimental Evaluation,' Mathematical Programming, vol. 73, no. 2, pp. 129-174, 1996 
    9. E. W. Dijkstra, 'A Note on Two Problems in Connection with Graphs,' Numerische Mathematik, I, pp. 269-271, 1959 
    10. F. B. Zhan and C. E. Noon, 'A Comparison Between Label-Setting and Label-Correcting Algorithms for Computing One-to-One Shortest Paths,' Journal of Geographic Information and Decision Analysis, vol. 4, no. 2, pp. 1-11, 2000 
  • 이 논문을 인용한 문헌 (1)

    1. Cheon, Seong-Kwon ; Kim, Geun-Deok ; Kim, Chong-Gun 2011. "A Speed-Based Dijkstra Algorithm for the Line Tracer Control of a Robot" 한국IT서비스학회지 = Journal of Information Technology Services, 10(4): 259~268     

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기