The Library
A ripple-spreading algorithm for the k shortest paths problem
Tools
Hu, Xiao-Bing, Wang, Ming, Hu, Di, Leeson, Mark S., Hines, Evor and Di Paolo, Ezequiel A. (2012) A ripple-spreading algorithm for the k shortest paths problem. In: 2012 3rd Global Congress on Intelligent Systems, GCIS 2012, Wuhan, China, 6-8 Nov 2012. Published in: Proceedings 2012 3rd Global Congress on Intelligent Systems pp. 202-208. ISBN 978-1-4673-3072-5. doi:10.1109/GCIS.2012.96
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.1109/GCIS.2012.96
Abstract
Inspired by the natural ripple-spreading phenomenon that occurs on a water surface, this paper proposes a novel ripple-spreading algorithm (RSA) for the k shortest paths problem (k-SPP). In nature, a ripple spreads at a constant speed in all directions, and the node closest to the source will be the first to be reached. This very simple principle forms the foundation of the proposed RSA. By mimicking the natural ripple-spreading phenomenon, the new algorithm starts an initial ripple from the source, and initial ripple triggers new ripples at other nodes as it spreads out. A new ripple can also trigger ripples at nodes farther away, until the destination is reached by k ripples. Then the kth ripple that reaches the destination determines the kth shortest path. The comparative experimental results illustrate the effectiveness and efficiency of the proposed algorithm.
Item Type: | Conference Item (Speech) | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Engineering > Engineering | ||||
Journal or Publication Title: | Proceedings 2012 3rd Global Congress on Intelligent Systems | ||||
Publisher: | IEEE | ||||
ISBN: | 978-1-4673-3072-5 | ||||
Book Title: | 2012 Third Global Congress on Intelligent Systems | ||||
Official Date: | 2012 | ||||
Dates: |
|
||||
Page Range: | pp. 202-208 | ||||
DOI: | 10.1109/GCIS.2012.96 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Conference Paper Type: | Speech | ||||
Title of Event: | 2012 3rd Global Congress on Intelligent Systems, GCIS 2012 | ||||
Type of Event: | Conference | ||||
Location of Event: | Wuhan, China | ||||
Date(s) of Event: | 6-8 Nov 2012 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |