Computing $$k$$ k shortest paths from a source node to each other node
| LEADER | caa a22 4500 | ||
|---|---|---|---|
| 001 | 60547026X | ||
| 003 | CHVBK | ||
| 005 | 20210128100326.0 | ||
| 007 | cr unu---uuuuu | ||
| 008 | 210128e20150801xx s 000 0 eng | ||
| 024 | 7 | 0 | |a 10.1007/s00500-014-1434-2 |2 doi |
| 035 | |a (NATIONALLICENCE)springer-10.1007/s00500-014-1434-2 | ||
| 245 | 0 | 0 | |a Computing $$k$$ k shortest paths from a source node to each other node |h [Elektronische Daten] |c [Guisong Liu, Zhao Qiu, Hong Qu, Luping Ji, Alexander Takacs] |
| 520 | 3 | |a The single-pair K shortest path (KSP) problem can be described as finding $$k$$ k least cost paths through a graph between two given nodes in a non-decreasing order, while single-source KSP algorithms aim to find KSPs from a given node to each other node. However, little effort has been devoted to the single-source KSP approaches. This paper proposes a novel single-source KSP algorithm in a given directed weighted graph where loops are allowed. The proposed method is designed to compute a set of shortest paths with exactly $$k$$ k distinctive lengths in a non-decreasing order. Meanwhile, it can also find all shortest paths with the length less than a given threshold. Inspired by water flowing principle, we imagine that there are waters flowing from a source node to each other node along edges at a constant speed. When the water reaches a node, the node will generate new waters flowing along its outgoing edges. By stepping back the traces of the water, the ordered shortest paths can be obtained. We also address the correctness and effectiveness of the method. Simulations are carried out using synthetic data and practical graph data, which demonstrate the considerable performance of the proposed approach especially for single-source KSP problems. | |
| 540 | |a Springer-Verlag Berlin Heidelberg, 2014 | ||
| 690 | 7 | |a K shortest path problem |2 nationallicence | |
| 690 | 7 | |a Single-pair KSP |2 nationallicence | |
| 690 | 7 | |a Single-source KSP |2 nationallicence | |
| 700 | 1 | |a Liu |D Guisong |u Computational Intelligence Laboratory, School of Computer Science and Engineering, University of Electronic Science and Technology of China, 610054, Chengdu, People's Republic of China |4 aut | |
| 700 | 1 | |a Qiu |D Zhao |u Computational Intelligence Laboratory, School of Computer Science and Engineering, University of Electronic Science and Technology of China, 610054, Chengdu, People's Republic of China |4 aut | |
| 700 | 1 | |a Qu |D Hong |u Computational Intelligence Laboratory, School of Computer Science and Engineering, University of Electronic Science and Technology of China, 610054, Chengdu, People's Republic of China |4 aut | |
| 700 | 1 | |a Ji |D Luping |u Computational Intelligence Laboratory, School of Computer Science and Engineering, University of Electronic Science and Technology of China, 610054, Chengdu, People's Republic of China |4 aut | |
| 700 | 1 | |a Takacs |D Alexander |u School of Computer Science and Communication, KTH Royal Institute of Technology, 100 44, Stockholm, Sweden |4 aut | |
| 773 | 0 | |t Soft Computing |d Springer Berlin Heidelberg |g 19/8(2015-08-01), 2391-2402 |x 1432-7643 |q 19:8<2391 |1 2015 |2 19 |o 500 | |
| 856 | 4 | 0 | |u https://doi.org/10.1007/s00500-014-1434-2 |q text/html |z Onlinezugriff via DOI |
| 898 | |a BK010053 |b XK010053 |c XK010000 | ||
| 900 | 7 | |a Metadata rights reserved |b Springer special CC-BY-NC licence |2 nationallicence | |
| 908 | |D 1 |a research-article |2 jats | ||
| 949 | |B NATIONALLICENCE |F NATIONALLICENCE |b NL-springer | ||
| 950 | |B NATIONALLICENCE |P 856 |E 40 |u https://doi.org/10.1007/s00500-014-1434-2 |q text/html |z Onlinezugriff via DOI | ||
| 950 | |B NATIONALLICENCE |P 700 |E 1- |a Liu |D Guisong |u Computational Intelligence Laboratory, School of Computer Science and Engineering, University of Electronic Science and Technology of China, 610054, Chengdu, People's Republic of China |4 aut | ||
| 950 | |B NATIONALLICENCE |P 700 |E 1- |a Qiu |D Zhao |u Computational Intelligence Laboratory, School of Computer Science and Engineering, University of Electronic Science and Technology of China, 610054, Chengdu, People's Republic of China |4 aut | ||
| 950 | |B NATIONALLICENCE |P 700 |E 1- |a Qu |D Hong |u Computational Intelligence Laboratory, School of Computer Science and Engineering, University of Electronic Science and Technology of China, 610054, Chengdu, People's Republic of China |4 aut | ||
| 950 | |B NATIONALLICENCE |P 700 |E 1- |a Ji |D Luping |u Computational Intelligence Laboratory, School of Computer Science and Engineering, University of Electronic Science and Technology of China, 610054, Chengdu, People's Republic of China |4 aut | ||
| 950 | |B NATIONALLICENCE |P 700 |E 1- |a Takacs |D Alexander |u School of Computer Science and Communication, KTH Royal Institute of Technology, 100 44, Stockholm, Sweden |4 aut | ||
| 950 | |B NATIONALLICENCE |P 773 |E 0- |t Soft Computing |d Springer Berlin Heidelberg |g 19/8(2015-08-01), 2391-2402 |x 1432-7643 |q 19:8<2391 |1 2015 |2 19 |o 500 | ||