Is the gas enough?
I have been trying to use the more general frameworks when I encounter dynamic programming questions, so I can demonstrate the power of abstraction later on.
Let be a directed acyclic graph. is the weight of an arc. A path is called a -deficient path if for all . Find the smallest , such that there is a -deficient path.
One can view this problem as how much gas would one require to travel from to . If one knows how much gas one can gain or lose between arcs.
Let be the value of the minimum deficiency path from to , and .
Because the graph is acyclic, there is a nice ordering allowing us to compute this nicely.
Note this is exactly the best weight problem under the semiring , where .
One should prove it’s a semiring before using it. Everything seems obvious except the distributive property of the operation. Here is a proof for one of the two distributive laws, the other is left as an exercise to the reader.
Can we extend the problem to directed graph with cycles? Yes. This semiring has the property that it is -closed for any graph for depending on and . It means we can’t keep going though a cycle and keep producing better solutions. We can run a generic single source shortest distance algorithm.
 L. Huang, Advanced dynamic programming in semiring and hypergraph frameworks, (2008).
 M. Mohri, Semiring frameworks and algorithms for shortest-distance problems, J. Autom. Lang. Comb. 7 (2002) 321–350.