An efficient label setting/correcting shortest path algorithm |
| |
Authors: | Antonio Sede?o-Noda and Carlos González-Martín |
| |
Institution: | (1) Department of Mathematical Sciences, Clemson University, Clemson, SC, 29634-0975 |
| |
Abstract: | We design a new label shortest path algorithm by applying the concept of a pseudo permanent label. This approach allows an algorithm to partition the set of nodes into two new sets: pseudo permanently labeled nodes and
its complementary set. From this point of view, this new label method can be considered as a label setting method. Moreover,
at least one node becomes permanently labeled when some nodes which belong to the set of pseudo permanently labeled nodes
are scanned in each iteration of the algorithm. In the case of networks with non-negative length arcs it is easy to prove
that this node has the minimum distance label among the non-pseudo permanently labeled nodes. On the other hand, it is not
known during the computation which pseudo permanently labeled nodes are permanently labeled. Therefore, all distance labels
are temporary and the algorithm becomes a label correcting method. Nevertheless, the proposed algorithm exhibits some nice
features, such as: (1) the time bound for the running of the algorithm for a network with n nodes and m arcs is O(nm); (2) the number of node scan operations in the algorithm is less than the number of these operations in the previous label
correcting algorithms as is observed in the computational experience; (3) the algorithm incorporates two new rules which allow
easy detection of a negative cycle in the network; (4) the algorithm is quite simple and very easy to implement, and does
not require sophisticated data structures; (5) the algorithm exhibits flexibility in the order in which the new pseudo permanently
labeled nodes are scanned. The above features are possible through the application of the pseudo permanent label concept. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|