Suppose we have a weighted, acyclic digraph, with positive and negative edge weights.


Is there an algorithm that determines whether there is a path of weight zero between vertices A and B? The Bellman-Form algorithm finds the path of smallest weight - is there another algorithm that determines the path of smallest absolute value weight?


Thanks,
Charles



Shortest absolute value of path in graph
It is NP-complete if $c$ is not specified. For a set of numbers $m\_1,\ldots,m\_t$ make a digraph with vertices $v\_0,v\_1,\ldots,v\_t$. From $v\_{i+1}$ to $v\_i$ put two edges, of length $m\_i$ and $-m\_i$, for each $i$. A path of zero length from $v\_0$ to $v\_t$ corresponds to a partition of $m\_1,\ldots,m\_t$ into two sets of equal size, which is a well known NP-complete problem (called PARTITION).


