본문 바로가기
  • Home
Basic Search

Shortest Path Search Scheme with a Graph of Multiple Attributes

  • Journal of The Korea Society of Computer and Information
  • Abbr : JKSCI
  • 2020, 25(12), pp.135-144
  • DOI : 10.9708/jksci.2020.25.12.135
  • Publisher : The Korean Society Of Computer And Information
  • Research Area : Engineering > Computer Science
  • Received : March 31, 2020
  • Accepted : October 6, 2020
  • Published : December 31, 2020

Jong Wan Kim 1,  Kwang-Jin Choi 2,  Oh Duk Shin 1

1삼육대학교
2삼육대학교 스미스교양대학

Accredited

ABSTRACT

In graph theory, the least-cost path is discovered by searching the shortest path between a start node and destination node. The least cost is calculated as a one-dimensional value that represents the difference in distance or price between two nodes, and the nodes and edges that comprise the lowest sum of costs between the linked nodes is the shortest path. However, it is difficult to determine the shortest path if each node has multiple attributes because the number of cost types that can appear is equal to the number of attributes. In this paper, a shortest path search scheme is proposed that considers multiple attributes using the Euclidean distance to satisfy various user requirements. In simulation, we discovered that the shortest path calculated using one-dimensional values differs from that calculated using the Euclidean distance for two-dimensional attributes. The user’s preferences are reflected in multi attributes and it was different from one-dimensional attribute. Consequently, user requirements could be satisfied simultaneously by considering multiple attributes.

Statistics

  • 221 Viewed
  • 55 Downloaded

Tools

Issue List

Citation status

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

This paper was written with support from the National Research Foundation of Korea.
Basic Search Advanced Search