The Library
Finding the k shortest paths by ripple-spreading algorithms
Tools
Hu, Xiao-Bing, Zhang, Chi, Zhang, Gong-Peng, Zhang, Ming-Kong, Li, Hang, Leeson, Mark S. and Liao, Jian-Qin (2020) Finding the k shortest paths by ripple-spreading algorithms. Engineering Applications of Artificial Intelligence, 87 . 103229. doi:10.1016/j.engappai.2019.08.023 ISSN 0952-1976.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1016/j.engappai.2019.08.023
Abstract
The shortest paths problem (-SPP) is fundamentally important to both theoretical and application researches on computational intelligence. Inspired by the natural ripple-spreading phenomenon that occurs on a water surface, this paper proposes a novel ripple-spreading algorithm (RSA). RSA differs from many existing methods which need to reconstruct route networks or to sweep the network for times, and it can identify the shortest paths by a single run of ripple relay race in the original route network. Besides the -SPP in normal route networks, the RSA can also be extended, without losing optimality and effectiveness, to some time-window networks (where various waiting behaviors at nodes are introduced) and dynamical networks (where the network topology and link costs may change over time due to factors such as moving obstacles and spreading disasters). For one-to-all -SPP, which aims to find all the shortest paths from a given source to every other node in a network (no matter with or without time windows at nodes, and no matter whether the network topology and link costs can change over time or not), the RSA can still find out all required solutions using only a single run, while the computational complexity is exactly the same as that for the one-to-one -SPP, i.e., , where is the number of links in the network, and is the average simulated time units for a ripple to travel through a link. The comparative experimental results illustrate the effectiveness and efficiency of the proposed RSA.
Item Type: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Engineering > Engineering | ||||||||
Journal or Publication Title: | Engineering Applications of Artificial Intelligence | ||||||||
Publisher: | Elsevier | ||||||||
ISSN: | 0952-1976 | ||||||||
Official Date: | January 2020 | ||||||||
Dates: |
|
||||||||
Volume: | 87 | ||||||||
Article Number: | 103229 | ||||||||
DOI: | 10.1016/j.engappai.2019.08.023 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||||
Description: | Free access but no reuse license indication |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |