FINDING THE SHORTEST PATHS AMONG CITIES IN JAVA ISLAND USING NODE COMBINATION BASED ON DIJKSTRA ALGORITHM

Publications

Share / Export Citation / Email / Print / Text size:

International Journal on Smart Sensing and Intelligent Systems

Professor Subhas Chandra Mukhopadhyay

Exeley Inc. (New York)

Subject: Computational Science & Engineering , Engineering, Electrical & Electronic

GET ALERTS

eISSN: 1178-5608

DESCRIPTION

9
Reader(s)
16
Visit(s)
0
Comment(s)
0
Share(s)

VOLUME 9 , ISSUE 4 (December 2016) > List of articles

FINDING THE SHORTEST PATHS AMONG CITIES IN JAVA ISLAND USING NODE COMBINATION BASED ON DIJKSTRA ALGORITHM

Bilqis Amaliah * / Chastine Fatichah * / Olyn Riptianingdyah

Keywords : Shortest path problem, Dijkstra algorithm, Node combination, Transportation problem.

Citation Information : International Journal on Smart Sensing and Intelligent Systems. Volume 9, Issue 4, Pages 2,219-2,236, DOI: https://doi.org/10.21307/ijssis-2017-961

License : (CC BY-NC-ND 4.0)

Received Date : 16-August-2016 / Accepted: 14-November-2016 / Published Online: 01-December-2016

ARTICLE

ABSTRACT

This study focuses on finding the shortest paths among cities in Java Island by repeatedly
combining the start node’s nearest neighbor to implement Dijkstra algorithm. Node combination is
used to find the shortest path among cities in Java by deleting the node nearest to the start node. The
use of memory by node combination is more efficient than the use of memory by the original Disjkstra
algorithm. The 46 cities in Java Island will be used to evaluate the performance of finding shortest
path. The experimental results show that the accuracy of node combination is 92.88% with the Google
Map as the reference. The successful implementation of algorithm in finding the shortest path on the
real problem is a good point; therefore, the algorithm can be developed to solve the transportation
network problem.

Content not available PDF Share

FIGURES & TABLES

REFERENCES

[1]. X. Zhang, Y. Zhang, “Rapid Physarum, Algorithm ForShortest Path Problem”, Applied
Soft Computing Vol. 23,pp.19–26, Oktober2014.
[2]. M. Farhanchi, R. Hassanzadeh, “A Modified Ant Colony System For Finding The
Expected Shortest Path In Networks With Variable Arc Lengths And Probabilistic Nodes”,
Applied Soft Computing Vol. 21,pp. 491–500, August 2014.
[3]. F. W. Trevizan, M. M. Veloso, “Depth-Based Short-Sighted Stochastic Shortest Path
Problems”, Artificial Intelligence, 216,pp. 179–205, 2014.
[4]. J. DeCarufel, C. Grimm, “A Note On The Unsolvability Of The Weighted Region Shortest
Path Problem”, Computational Geometry, Vol. 47, issue 7, pp. 724–727, August 2014.
[5]. A. K. Ziliaskopoulos, F. D. Mandanas, “An Extension Of Labeling Techniques For Finding
Shortest Path Trees”, European Journal of Operational Research, Vol. 198, issue 1,pp.63–
72, October 2009.
[6]. C. Gao, C. Yan, “An Amoeboid Algorithm For Solving Linear Transportation Problem”,
Physica A: Statistical Mechanics and its Applications, Vol. 398, pp. 179–186, March 2014.
[7]. E. Amaldi, A. Capone, “Energy-Aware IP Traffic Engineering With Shortest Path
Routing”, Computer Networks, Vol. 57, issue 6, pp. 1503–1517, April 2013.
[8]. Y. Zhang, Z. Zhang, “A Biologically Inspired Solution For Fuzzy Shortest Path Problems”,
Applied Soft Computing,Vol. 13, Issue 5, pp. 2356–2363, May 2013.
[9]. A. Nazemi, F. Omidi, “An Efficient Dynamic Model For Solving The Shortest Path
Problem”, Transportation Research Part C: Emerging Technologies, Vol.26,pp.1–19,
January 2013.
[10]. W. Peng, X. Hu, “A Fast Algorithm to Find All-Pairs Shortest Paths in Complex
Networks”, Procedia Computer Science, Vol. 9, pp. 557 – 566, 2012.
[11]. R. Hassanzadeh, I. Mahdavi, “A Genetic Algorithm For Solving Fuzzy Shortest Path
Problems With Mixed Fuzzy Arc Lengths”, Mathematical and Computer Modelling, Vol.
57, Issue 1-2, pp. 84 – 99, January 2013.
[12]. W. Shu-Xi ,“The Improved Dijkstra's Shortest Path Algorithm and Its Application”,
Procedia Engineering, Vol. 29, pp. 1186 – 1190, 2012.
[13]. S. Subramanian, R. Tamassia, “An Efficient Parallel Algorithm for Shortest Paths inPlanar
Layered Digraphs”, Algorithmica, Vol. 14, Issue 4, pp. 322-339, October 1995.
[14]. J. Joaci, A. R. Backes, “Texture Analysis And Classification Using Shortest Paths In
Graphs”, Pattern Recognition Letters, Vol. 34, Issue 11, pp. 1314–1319, August 2013.
[15]. J. Quan Li, “Match Bus Stops To A Digital Road Network By The Shortest Path Model”,
Transportation Research Part C: Emerging Technologies, Vol. 22, pp. 119–131, June 2012.
[16]. C. Bode, S. Irnich, “The Shortest-Path Problem With Resource Constraints With (K,2) –
Loop Elimination And Its Application To The Capacitated Arc-Routing Problem”,
European Journal of Operational Research, Vol. 238, Issue 2, pp. 415–426, October 2014.
[17]. F. J. Pulido, L. Mandow, “MultiobjectiveShortest Path Problems With Lexicographic Goal-
BasedPreferences”, European Journal of Operational Research, Vol. 239, Issue 1, pp. 89–
101, November 2014.
[18]. Y. Xi, L. Schwiebert, “Privacy Preserving Shortest Path Routing With An Applicationto
Navigation”, Pervasive and Mobile Computing, Vol. 13, pp. 142–149, August 2014.
[19]. C. L. Azevedo, J. L. Cardoso, “Vehicle Tracking Using The K-Shortest Paths Algorithm
And DualGraphs”, Transportation Research Procedia, Vol. 1, Issue 1, pp. 3 – 11, 2014.
[20]. M. Baxter, T. Elgindy, “Incremental Network Design With Shortest Paths”, European
Journal of Operational Research, Vol. 238, Issue 3, pp. 675–684, November 2014.
[21]. L. Sitanayah, K. N. Brown, “A Fault-Tolerant Relay Placement Algorithm For Ensuring
Kvertex-Disjoint Shortest Paths In Wireless Sensor Networks”, Ad Hoc Networks, Vol. 23,
pp. 145–162, December 2014.
[22]. B. Doerr, D. Johannsen, “More Effective Crossover Operators For The All-Pairs Shortest
Path Problem”, Theoretical Computer Science, Vol. 471, pp. 12–26, February 2013.
[23]. F. Chu, S. Chen, “Optimal Design Of Pipeline Based On The Shortest Path”, Physics
Procedia, Vol. 33, pp. 216 – 220, 2012.
[24]. X. Lu, M. Camitz, “Finding The Shortest Paths By Node Combination”,Applied
Mathematics and Computation, Vol. 217,Issue 13, pp. 6401–6408, March 2011.
[25] G. Yu, H.Song, “Unmanned Aerial Vehicle Path Planning Based On TLBO Algorithm”,
International Journal On Smart Sensing And Intelligent Systems, Vol. 7, No. 3, pp. 1310 –
1325, September 2014.
[26] Z. Cui, Y. Zhao, “An Energy-Efficient Routing For Vehicular Ad Hoc Networks Using
Real-Time Perception Of Node Information” International Journal On Smart Sensing And
Intelligent Systems Vol. 8, No. 2, pp. 1142– 1161, January 2015.
[27] C. J. Zhu, K.Y Lam, “Approximate Path Searching For Supporting Shortest Path Queries
On Road Networks”, Information Science, Vol. 325, pp. 409-428, December 2015.
[28] F.J. Pulido, L. Mandow, “Dimensionality Reduction In Multiobjective Shortest Path
Search”, Computers & Operations Research, Vol. 64, pp. 60-70, December 2015.

EXTRA FILES

COMMENTS