@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.