KJCKorea
Journal Central

@article{ART001898125},
author={Sang-Un, Lee},
title={A Point-to-Point Shortest Path Search Algorithm in an Undirected Graph Using Minimum Spanning Tree},
journal={Journal of The Korea Society of Computer and Information},
issn={1598-849X},
year={2014},
volume={19},
number={7},
pages={103-111}

TY - JOUR
AU - Sang-Un, Lee
TI - A Point-to-Point Shortest Path Search Algorithm in an Undirected Graph Using Minimum Spanning Tree
JO - Journal of The Korea Society of Computer and Information
PY - 2014
VL - 19
IS - 7
PB - The Korean Society Of Computer And Information
SP - 103
EP - 111
SN - 1598-849X
AB - This paper proposes a modified algorithm that improves on Dijkstra’s algorithm by applying it topurely two-way traffic paths, given that a road where bi-directional traffic is made possible shallbe considered as an undirected graph. Dijkstra’s algorithm is the most generally utilized form ofshortest-path search mechanism in GPS navigation system. However, it requires a large amount ofmemory for execution for it selects the shortest path by calculating distance between the starting node and every other node in a given directed graph. Dijkstra’s algorithm, therefore, mayoccasionally fail to provide real-time information on the shortest path. To rectify theaforementioned shortcomings of Dijkstra’s algorithm, the proposed algorithm creates conditionsfavorable to the undirected graph. It firstly selects the shortest path from all path vertices exceptfor the starting and destination vertices. It later chooses all vertex-outgoing edges that coincidewith the shortest path setting edges so as to simultaneously explore various vertices. When testedon 9 different undirected graphs, the proposed algorithm has not only successfully found theshortest path in all, but did so by reducing the time by 60% and requiring less memory.
KW - Undirected graph;Shortest path;Dijkstra algorithm;GPS navigation system;Point-to-point search
DO -
UR -
ER -

Sang-Un, Lee. (2014). A Point-to-Point Shortest Path Search Algorithm in an Undirected Graph Using Minimum Spanning Tree. Journal of The Korea Society of Computer and Information, 19(7), 103-111.

Sang-Un, Lee. 2014, "A Point-to-Point Shortest Path Search Algorithm in an Undirected Graph Using Minimum Spanning Tree", Journal of The Korea Society of Computer and Information, vol.19, no.7 pp.103-111.

Sang-Un, Lee "A Point-to-Point Shortest Path Search Algorithm in an Undirected Graph Using Minimum Spanning Tree" Journal of The Korea Society of Computer and Information 19.7 pp.103-111 (2014) : 103.

Sang-Un, Lee. A Point-to-Point Shortest Path Search Algorithm in an Undirected Graph Using Minimum Spanning Tree. 2014; 19(7), 103-111.

Sang-Un, Lee. "A Point-to-Point Shortest Path Search Algorithm in an Undirected Graph Using Minimum Spanning Tree" Journal of The Korea Society of Computer and Information 19, no.7 (2014) : 103-111.

Sang-Un, Lee. A Point-to-Point Shortest Path Search Algorithm in an Undirected Graph Using Minimum Spanning Tree. Journal of The Korea Society of Computer and Information, 19(7), 103-111.

Sang-Un, Lee. A Point-to-Point Shortest Path Search Algorithm in an Undirected Graph Using Minimum Spanning Tree. Journal of The Korea Society of Computer and Information. 2014; 19(7) 103-111.

Sang-Un, Lee. A Point-to-Point Shortest Path Search Algorithm in an Undirected Graph Using Minimum Spanning Tree. 2014; 19(7), 103-111.

Sang-Un, Lee. "A Point-to-Point Shortest Path Search Algorithm in an Undirected Graph Using Minimum Spanning Tree" Journal of The Korea Society of Computer and Information 19, no.7 (2014) : 103-111.