(Shortest Path Problems with Losses) Consider a vehicle routing/shortest path-like problem where a vehicle wants to go on a forward path from an origin node 1 to a destination node t in a graph that has no forward cycles. For each arc (i, j) there is a given length aij , but there is also a given probability pij ∈ [0, 1] that the vehicle will be destroyed in crossing the arc. The length of a path is now a random variable, and is equal to the sum of the arc lengths on the path up to the time the vehicle reaches its destination or gets destroyed, whichever comes first. We want to find a forward path P = (1, i1,...,ik, t) whose expected length, given by
