# 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 $D=(V,A)$ be a directed acyclic graph. $w(e)$ is the weight of an arc. For an $α≥0$, a $s−t$ path $e_{1},…,e_{m}$ is called a $α$-deficient path if $∑_{i=1}w(e_{i})+α≥0$ for all $1≤k≤m$. Find the smallest $α$, such that there is a $α$-deficient $s−t$ path.

One can view this problem as how much gas would one require to travel from $s$ to $t$. If one knows how much gas one can gain or lose between arcs.

Let $D(v)$ be the value of the minimum deficiency path from $v$ to $t$, and $D(t)=0$.

$D(v)=(v,u)∈Amin max(D(u)−w((v,u)),0)$

Because the graph is acyclic, there is a nice ordering allowing us to compute this nicely.

Note this is exactly the best weight problem[1] under the semiring $(R∪{∞},min,⊗,∞,0)$, where $a⊗b=max(a−b,0)$.

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.

$(a⊕b)⊗c =max(min(a,b)−c,0)=max(min(a−c,b−c),0)=min(max(a−c,0),max(b−c,0))=(a⊗c)⊕(b⊗c) $

Can we extend the problem to directed graph with cycles? Yes. This semiring has the property that it is $k$-closed for any graph $G$ for $k$ depending on $G$ and $w$. 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[2].

# References

**Advanced dynamic programming in semiring and hypergraph frameworks**, (2008).

**Semiring frameworks and algorithms for shortest-distance problems**, J. Autom. Lang. Comb. 7 (2002) 321–350.