ScholarLens Back to search
2007•Unpublished venueRequires access

An Improved Dijkstra Algorithm Based on Pairing Heap

Shen Pai-wei

Open publisher page 1 citations

Abstract

Dijkstra is a classic algorithm to compute the shortest-path in GIS network analysis system.To improve the algorithm efficiency and save memory usage,this paper proposes a new data structure,called heap,to implement the priority queue.So that the Dijkstra algorithm can use pairing heap.This paper gives out the implementation details and algorithm's flow via studying the basic function of paring heap,and then analyses the algorithm's complexity.This new algorithm has applied in VegaGIS and obtains good results.

About this research paper

What this paper is about

Dijkstra is a classic algorithm to compute the shortest-path in GIS network analysis system.To improve the algorithm efficiency and save memory usage,this paper proposes a new data structure,called heap,to implement the priority queue.So that the Dijkstra algorithm can use pairing heap.This paper gives out the implementation details and algorithm's flow via studying the basic function of paring heap,and then analyses the algorithm's complexity.This new algorithm has applied in VegaGIS and obtains good results.

Why it matters

OpenAlex reports 1 citations for this work. Citation counts describe recorded attention and do not establish research quality.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available abstract

Dijkstra is a classic algorithm to compute the shortest-path in GIS network analysis system.To improve the algorithm efficiency and save memory usage,this paper proposes a new data structure,called heap,to implement the priority queue.So that the Dijkstra algorithm can use pairing heap.This paper gives out the implementation details and algorithm's flow via studying the basic function of paring heap,and then analyses the algorithm's complexity.This new algorithm has applied in VegaGIS and obtains good results.

Key concepts: Dijkstra's algorithm, Heap (data structure), Computer science, Priority queue, Algorithm, Shortest path problem, Suurballe's algorithm, Yen's algorithm

Related papers

Related paper 1Related paper 2Related paper 3
Back to paper searchBrowse research topicsOriginal source
An Improved Dijkstra Algorithm Based on Pairing Heap — Research Paper | ScholarLens