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

Background

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: A → R is the weight function, δ > 0 is a constant such that δ ≤ W(a) < +∞ for all a ∈ A, and finally b is a constant integer such that 0 < b < |V| and |{v | (u, v) ∈ A or (v, u) ∈ A}| ≤ b for all u ∈ V. Suppose we want to find a shortest s-t (directed) path in G, where s ∈ V is a specified starting node and t ∈ V is a specified terminal node. Further suppose a heuristic function exists h: V→ R such that h(v) ≥ 0 for all v ∈ V, 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.