본문 바로가기
  • Home

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
  • Abbr : JKSCI
  • 2014, 19(7), pp.103-111
  • Publisher : The Korean Society Of Computer And Information
  • Research Area : Engineering > Computer Science

Sang-Un, Lee 1

1강릉원주대학교

Accredited

ABSTRACT

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.

Citation status

* References for papers published after 2022 are currently being built.