Name
Abstract | ||
|---|---|---|
In this paper, the problem of finding a shortest path tree rooted at a given source node on a directed graph (SPT) is considered. A new efficient algorithm based on a primal-dual approach is presented, which improves both the convergence and the complexity of the best known auction-like algorithm. It uses the virtual source (VS) concept based on the following consideration: when a node i is visited for the first time by any algorithm which preserves verified the dual admissibility conditions, then the shortest path (SP) from the source node to i is found. Therefore, the SP from the source to the remaining nodes may be computed by considering i as a “virtual source”.We propose a very efficient implementation of an auction-like algorithm that uses this concept and enables us to obtain a computational cost of O(n2), where n is the number of nodes.Numerical experiments are reported showing that the new method outdoes previously proposed auction-like algorithms and is highly competitive with other state-of-art SP approaches. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1023/A:1025750631443 | Comp. Opt. and Appl. |
Keywords | Field | DocType |
shortest path,network optimization,auction technique | Mathematical optimization,Shortest path problem,Constrained Shortest Path First,Yen's algorithm,Suurballe's algorithm,Shortest Path Faster Algorithm,Auction algorithm,Widest path problem,Mathematics,K shortest path routing | Journal |
Volume | Issue | ISSN |
26 | 2 | 1573-2894 |
Citations | PageRank | References |
0 | 0.34 | 9 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| R. Cerulli | 1 | 252 | 23.85 |
| Paola Festa | 2 | 287 | 25.32 |
| Giancarlo Raiconi | 3 | 118 | 15.08 |