TY - JOUR
T1 - On solving shortest paths with a least-squares primal-dual algorithm
AU - Wang, I. Lin
N1 - Funding Information:
I.-Lin Wang was partially supported by the National Science Council of Taiwan under Grant NSC93-2213-E006-096.
Copyright:
Copyright 2008 Elsevier B.V., All rights reserved.
PY - 2008/4
Y1 - 2008/4
N2 - Recently a new least-squares primal-dual (LSPD) algorithm, that is impervious to degeneracy, has effectively been applied to solving linear programming problems by Barnes et al., 2002. In this paper, we show an application of LSPD to shortest path problems with nonnegative arc length is equivalent to the Dijkstra's algorithm. We also compare the LSPD algorithm with the conventional primal-dual algorithm in solving shortest path problems and show their difference due to degeneracy in solving the 1-1 shortest path problems.
AB - Recently a new least-squares primal-dual (LSPD) algorithm, that is impervious to degeneracy, has effectively been applied to solving linear programming problems by Barnes et al., 2002. In this paper, we show an application of LSPD to shortest path problems with nonnegative arc length is equivalent to the Dijkstra's algorithm. We also compare the LSPD algorithm with the conventional primal-dual algorithm in solving shortest path problems and show their difference due to degeneracy in solving the 1-1 shortest path problems.
UR - http://www.scopus.com/inward/record.url?scp=47749142833&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=47749142833&partnerID=8YFLogxK
U2 - 10.1142/S0217595908001699
DO - 10.1142/S0217595908001699
M3 - Article
AN - SCOPUS:47749142833
SN - 0217-5959
VL - 25
SP - 135
EP - 150
JO - Asia-Pacific Journal of Operational Research
JF - Asia-Pacific Journal of Operational Research
IS - 2
ER -