We wish to select the set of edges with minimal weight, subject to the constraint that this set forms a path from "s" to "t" (represented by the equality constraint: for all vertices except "s" and "t" the number of incoming and outcoming edges that are part of the path must be the same (i.e., that it should be a path from s to t). This LP has the special property that it is integral; more specifically, every basic optimal solution (when one exists) has all variables equal to 0 or 1, and the set of edges whose variables equal 1 form an "s"-"t" dipath. See Ahuja et al. for one proof, although the origin of this approach dates back to mid-20th century. The dual for this linear program is and feasible duals correspond to the concept of a consistent heuristic for the A* algorithm for shortest paths. For any feasible dual "y" the reduced costs formula_27 are nonnegative and A* essentially runs Dijkstra's algorithm on these reduced costs. Many problems can be framed as a form of the shortest path for some suitably substituted notions of addition along a path and taking the minimum. The general approach to these is to consider the two operations to be those of a semiring. Semiring multiplication is done along the path, and the addition is between paths. This general framework is known as the algebraic path problem. Most of the classic shortest-path algorithms (and new ones) can be formulated as solving linear systems over such algebraic structures. More recently, an even more general framework for solving these (and much less obviously related problems) has been developed under the banner of valuation algebras. In real-life situations, the transportation network is usually stochastic and time-dependent. In fact, a traveler traversing a link daily may experiences different travel times on that link due not only to the fluctuations in travel demand (origin-destination matrix) but also due to such incidents as work zones, bad weather conditions, accidents and vehicle breakdowns. As a result, a stochastic time-dependent (STD) network is a more realistic representation of an actual road network compared with the deterministic one. Despite considerable progress during the course of the past decade, it remains a controversial question how an optimal path should be defined and identified in stochastic road networks. In other words, there is no unique definition of an optimal path under uncertainty. One possible and common answer to this question is to find a path with the minimum expected travel time.