Shortest Path - Finding Algorithm using Multiple Dynamic - Range Queue ( MDRQ )


The KIPS Transactions:PartA, Vol. 8, No. 2, pp. 179-188, Jun. 2001
10.3745/KIPSTA.2001.8.2.179,   PDF Download:

Abstract

We analyze the property of candidate node set in the network graph, and propose an algorithm to decrease shortest path-finding computation time by using multiple dynamic-range queue (MDRQ) structure. This MDRQ structure is newly created for effective management of the candidate node set. The MDRQ algorithm is the shortest path-finding algorithm that varies range and size of queue to be used in managing candidate node set, in considering the properties that distribution of candidate node set is constant and size of candidate node set rapidly change. This algorithm belongs to label-correcting algorithm class. Nevertheless, because re-entering of candidate node can be decreased, the shortest path-finding computation time is noticeably decreased. Through the experiment, the MDRQ algorithm is same or superior to the other label-correcting algorithms in the graph which re-entering of candidate node didn't frequently happened. Moreover the MDRQ algorithm is superior to the other label-correcting algorithms and is about 20 percent superior to the other label-setting algorithms in the graph which re-entering of candidate node frequently happened.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
T. J. Kim and M. H. Han, "Shortest Path - Finding Algorithm using Multiple Dynamic - Range Queue ( MDRQ )," The KIPS Transactions:PartA, vol. 8, no. 2, pp. 179-188, 2001. DOI: 10.3745/KIPSTA.2001.8.2.179.

[ACM Style]
Tae Jin Kim and Min Hong Han. 2001. Shortest Path - Finding Algorithm using Multiple Dynamic - Range Queue ( MDRQ ). The KIPS Transactions:PartA, 8, 2, (2001), 179-188. DOI: 10.3745/KIPSTA.2001.8.2.179.