Abstract
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.
| Original language | English |
|---|---|
| Pages (from-to) | 135-150 |
| Number of pages | 16 |
| Journal | Asia-Pacific Journal of Operational Research |
| Volume | 25 |
| Issue number | 2 |
| DOIs | |
| Publication status | Published - 2008 Apr |
All Science Journal Classification (ASJC) codes
- Management Science and Operations Research
Fingerprint
Dive into the research topics of 'On solving shortest paths with a least-squares primal-dual algorithm'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver