A Note on the Connection Between the Primal-Dual and the A* Algorithm

A Note on the Connection Between the Primal-Dual and the A* Algorithm

Xugang Ye, Shih-Ping Han, Anhua Lin
DOI: 10.4018/joris.2010101305
(Individual Articles)
No Current Special Offers


The primal-dual algorithm for linear programming is very effective for solving network flow problems. For the method to work, an initial feasible solution to the dual is required. In this article, we show that, for the shortest path problem in a positively weighted graph equipped with a consistent heuristic function, the primal-dual algorithm will become the well-known A* algorithm if a special initial feasible solution to the dual is chosen. We also show how the improvements of the dual objective are related to the A* iterations.
Article Preview


We consider a directed, positively weighted simple graph denoted as G = (V, A, W, δ, b), where V is the set of nodes, A is the set of arcs, W: AR is the weight function, δ > 0 is a constant such that δW(a) < +∞ for all aA, and finally b is a constant integer such that 0 < b < |V| and |{v | (u, v) ∈ A or (v, u) ∈ A}| ≤ b for all uV. Suppose we want to find a shortest s-t (directed) path in G, where sV is a specified starting node and tV is a specified terminal node. Further suppose a heuristic function exists h: VR such that h(v) ≥ 0 for all vV, h(t) = 0, and W(u, v) + h(v) ≥ h(u) for all (u, v) ∈ A. h is called consistent heuristic. According to Hart et al. (1968), Hart et al. (1972), Nilsson (1980), and Pearl (1984), the A* algorithm that uses such h is complete, that is, it can find a shortest s-t path in G as long as there exists an s-t path in G. The algorithm can be stated as follows. It searches from s to t.

Complete Article List

Search this Journal:
Volume 15: 1 Issue (2024)
Volume 14: 1 Issue (2023)
Volume 13: 2 Issues (2022)
Volume 12: 4 Issues (2021)
Volume 11: 4 Issues (2020)
Volume 10: 4 Issues (2019)
Volume 9: 4 Issues (2018)
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing