An Efficient Shortest Path Algorithm: Multi-Destinations in an Indoor Environment

Symmetry

TanKim Geok¹  Sharif Ahmed¹  Ferdous Hossain¹  Azlan Abdaziz¹  C.P. Tso¹  Hin-Yong Wong²  Mina Asaduzzaman³  MdAhsanul Bari³  Shohel Sayeed³ 

[1] Faculty of Engineering and Technology, Multimedia University, Melaka 75450, Malaysia;Faculty of Engineering, Multimedia University, Cyberjaya 63100, Malaysia;Faculty of Information Science and Technology, Multimedia University, Melaka 75450, Malaysia;

关键词: graph;    multi-destination;    road network;    shortest path;    indoor;   

DOI  :  10.3390/sym13030421

来源: DOAJ

【 摘 要 】

The shortest path-searching with the minimal weight for multiple destinations is a crucial need in an indoor applications, especially in supermarkets, warehouses, libraries, etc. However, when it is used for multiple item searches, its weight becomes higher as it searches only the shortest path between the single sources to each destination item separately. If the conventional Dijkstra algorithm is modified to multi-destination mode then the weight is decreased, but the output path is not considered as the real shortest path among multiple destinations items. Our proposed algorithm is more efficient for finding the shortest path among multiple destination items with minimum weight, compared to the single source single destination and modified multi-destinations of Dijkstra’s algorithm. In this research, our proposed method has been validated by real-world data as well as by simulated random solutions. Our advancement is more applicable in indoor environment applications based on multiple items or destinations searching.

【 授权许可】

Unknown