On solving shortest paths with a least-squares primal-dual algorithm

Research output: Contribution to journalArticlepeer-review


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 languageEnglish
Pages (from-to)135-150
Number of pages16
JournalAsia-Pacific Journal of Operational Research
Issue number2
Publication statusPublished - 2008 Apr

All Science Journal Classification (ASJC) codes

  • Management Science and Operations Research


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