In this thesis, an improved new heap algorithm called Pairing heap to optimize Dijkstra's algorithm is presented. Dijkstra's algorithm is used in routing for single source shortest path problem. The core step of Dijkstra's algorithm is "finding the minimum adjacent node to the source node and deleting it from the node table". But the Dijkstra's algorithm has the problem that it takes too long time to traverse the node table and delete the minimum node and update the node table. So Pairing heap's operations are added to Dijkstra's algorithm to solve the problem in this thesis. The Pairing heap's merge is to merge two heaps together and let the little one be the parent, merge the new node as a heap with a single node into the heap, decrease_key is to cut the node and its children out of the tree, then merge the rest of the heap again, and delete_min is to delete the minimum node and merge the rest of the children, insert is to insert a new node. The operations are simpler than the Fibonacci heap and the Binary heap. And then it is optimized by cache theory. Experiment for 3 map data is taken, and the experimented results show that the Pairing heap works much better than Fibonacci heap and Binary heap as the number of nodes get growing.
본 눈문에서는 Dijkstra 알고리듬을 최적화하기 위해서 Pairing heap 이라고 하는 알고리듬을 사용한 성능이 개선된 알고리듬을 연구하였다. 그런데 Dijkstra 알고리듬은 한 시점에서 목적지 까지 최단경로를 찾는데 사용되는 방법이다. Dijkstra 알고리듬 에서는 인접한 최소거리의 절점을 찾고 절점 표 에서 이 절점을 지우는 방법을 사용하는데, 이 방법을 개선하여 최적이 되도록 하기 위해서 Heap 이론을 적용하였다. 적용한 결과 기존의 방법인 Binary heap 와 Fibonacci heap방법보다도 알고리듬이 간단하고 성능이 더욱 효율적이 있다. 본 논문에서는 Pairing heap 방법을 Binary heap, Fibonacci heap 와 이론적으로 분석하고 실험을 하여 비교하였다. 실험을 한 결과, 본 논문의 방법이 이들 방법보다도 더욱 우수함을 알수 있었다. 그리고 Cache 이론을 사용하여 최적화하여 3 GIS 지도자료를 실험하였습니다.