Shortest Path Search Scheme with a Graph of Multiple Attributes
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
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.
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.
참고문헌 (12)
- M. H. Alsuwaiyel, "Algorithms: Design Techniques and Analysis Vol. 14" (2016), World Scientific
- M. A. Reba, "Puzzles, Paradoxes, and Problem Solving: An Introduction to Mathematical Thinking" (2015), CRC Press
- R. Oosumi, "Novel single-objective optimization problem and Firefly Algorithm-based optimization method", IEEE International Conference on Systems, Man, and Cybernetics(SMC), pp.1011~1015 (2016)
- Md. Almash Alam, "Finding Shortest Path for Road Network Using Dijkstra’s Algorithm", Bangladesh Journal of Multidisciplinary Scientific Research, 1(2), pp.41~45 (2019), Centre for Research on Islamic Banking and Finance and Business[DOI]
- L. Parungao, "Dijkstra Algorithm Based Intelligent Path Planning with Toplogical Map and Wireless Communication", ARPN Journal of Engineering and Applied Sciences, 13(8), pp.2753~2763 (2018)
- M. Iqbal, "A Fast and Reliable Dijkstra Algorithm for Online Shortest Path", SSRG International Journal of Computer Science and Engineering, 5(12), pp.24~27 (2018)[DOI]
- J. Carey, "C++ Data Structures and Algorithm Design Principles" (2019), Packt Publishing
- Léo Morin, "Generalized Euclidean Distances for Elasticity Tensors", Journal of Elasticity, 138(2), pp.221~232 (2020), Springer Science and Business Media LLC[DOI]
- Yefim Dinitz, "Hybrid Bellman–Ford–Dijkstra algorithm", Journal of Discrete Algorithms, 42, pp.35~44 (2017), Elsevier BV[DOI]
- Kehong Zhang, "A novel algorithm for TOP-K optimal path on complex multiple attribute graph", International Journal of Embedded Systems, 12(4), pp.510~521 (2020), Inderscience Publishers[DOI]
- Loïc Bidoux, "Planning with preferences using Multi-Attribute Utility Theory along with a Choquet Integral", Engineering Applications of Artificial Intelligence, 85, pp.808~817 (2019), Elsevier BV[DOI]