방향그래프의 점대점 최단경로 탐색 알고리즘

국문 초록 (Abstract)

본 논문은 실시간 GPS 항법시스템에서 최단 경로를 탐색하는데 일반적으로 적용되고 있는 Dijkstra 알고리즘의 문제점을 개선한 알고리즘을 제안하였다. Dijkstra 알고리즘은 출발 노드부터 시작하여 그래프의 모든 노드에 대한 최단 경로를 결정하기 때문에 일반적으로 노드의 수 - 1회를 수행해야 하며, 알고리즘 수행에 많은 메모리가 요구된다. 따라서 Dijkstra 알고리즘은 복잡한 도시의 도로에서 목적지 까지 최단 경로를 탐색하여 실시간으로 정보를 제공하지 못할 수도 있다. 이러한 문제점을 해결하고자, 본 논문에서는 먼저 출발과 목적지 노드를 제외한 경로 노드들의 최단 경로 (유입과 유출 최소 가중치 호 선택)를 결정하고, 출발 노드부터 시작하여 노드 유출 호들에 대해 경로 노드의 최단 경로와 일치하는 호들을 모두 선택하는 방식으로 한번에 다수의 노드들을 탐색하는 방법을 택하였다. 14개의 다양한 방향 그래프에 제안된 알고리즘을 적용한 결과 모두 최단 경로를 탐색하는데 성공하였다. 또한, 수행 속도 측면에서 Dijkstra 알고리즘보다 2배에서 3배 정도 빠른 결과를 얻었으며, 알고리즘 수행에 필요한 메모리도 적게 요구되었다.

다국어 초록 (Multilingual Abstract)

This paper suggests an algorithm that improves the disadvantages of the Dijkstra algorithm that is commonly used in GPS navigation system, searching for the shortest path. Dijkstra algorithm, first of all, requires much memory for the performance of the algorithm. It has to carry out number of node minus 1, since it determines the shortest path from all the nodes in the graph, starting from the first node. Therefore, Dijkstra algorithm might not be able to provide the information on every second, searching for the shortest path between the roads of the congested city and the destination. In order to solve these problems, this paper chooses a method of searching a number of nodes at once by means of choosing the shortest path of all the path nodes (select of minimum weight arc in-degree and out-degree), excluding the departure and destination nodes, and of choosing all the arcs that coincide with the shortest path of the path nodes, from all the node outgoing arcs starting from the departure node. On applying the suggested algorithm to 14 various digraphs, we succeeded to search the shortest path. In addition, the result was obtained at the speed of 2 to 3 times faster than that of Dijkstra algorithm, and the memory required was less than that of Dijkstra algorithm.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 관련 연구와 연구 배경
• 3. Sulee SP 알고리즘
• 4. 알고리즘 적용성 평가
• 5. 결론 및 향후 연구과제
• 참고문헌
• 저자소개

참고문헌 (Reference)

1 "강원도립대학 컴퓨터응용과 전임 강사2004년～2007.2 원주대학 여성교양과 조교수2007.3～현재 소프트웨어 개발 방법론 분석과 설계 방법론 소프트웨어 시험 및 품질보증" 한국항공대학교 항공전자공학과 경상대학교 컴퓨터과학과 경상대학교 컴퓨터과학과 강릉대학교 컴퓨터공학부 멀티미디어정보공학 전공 조교수관심분야 1-, 1987년1997년2001년1992년～2002년국방품질관리소항공전자장비소프트웨어품질보증담당2003년

2 "Three Fatest Shortest Path Algorithms on Real Road Networks Data Structures and Procedures" 1 (1): 69-82, 1997.

3 "Shortest Connection Networks and Some Generalisations" 36 : 1389-1401, 1957.

4 "Real Time GPS Navigation System" 2004.

5 "Otakar Borvka on Minimum Spanning Tree Problem" 233 : 2001.

6 "O Jistem Problemu Minimalnim" 3 (3): 37-58, 1926.

7 "Network Optimization Dijkstras Algorithm for the Shortest Path Problem" http://www.mit.edu/~jorlin/15.082/Lectures/ 05 Dijkstra.ppt 2003.

8 "Mathematical Programming" Dept. Information Science and Intelligent Systems, The University of Tokushima 2005

9 "Introduction to Algorithms" MIT Press and McGraw Hill 2001

10 "Discrete Mathematics" http://www. maths.mq.edu. au/~wchen/lndmfolder/lndm.html 2003.

11 "Dijkstra's Algorithm" http:// en. wikipedia.org/wiki/Dijkstra_algorithm Wikimedia Foundation Inc. 2007.

12 "CS 221 Data Structures" Computer Science, University of Alabama in Huntsville 2002.

13 "COS 226 Algorithms and Data Structures" Department of Computer Science, Princeton University 2004.

14 "COP 3503 Computer Science II Introduction to Graphs" http://www.cs.ucf.edu/ courses/cop3503/summer04 2004

15 "CIS 780 Analysis of Algorithms" http://www.cse. ohio-state.edu/~wenger/cis780/shortest_path.pdf 2004.

16 "Applications of Combinational Optimization Optimal Paths and Trees" School of Information Technology and Engineering (SITE) University of Ottawa Canada 2005.

17 "A Walk Over the Shortest Path Dijkstra's Algorithm Viewed as Fixed Point Computation" 2000.

18 "A Shortest Path Algorithm for Real Road Network Based on Path Overlap" Department of Civil Engineering Institute of Transportation Studies University of California 2005

19 "A Note on Two Problems in Connection with Graphs" 1 : 269-271, 1959.