ON ASSOCIATIVE SHORTEST PATH PROBLEMS

We consider a wide class of shortest path problems in acyclic digraphs. In the problems, the length of a path is defined by using an associative binary operation. We derive recursive equations in dynamic programming for the problems, which involve additive, multiplicative, multiplicative-additive, minimum and fractional shortest path problems. A necessary and sufficient condition and two sufficient conditions for the recursive equation to have a solution are given because for all problems the recursive equation does not hold. In case the equation has a solution, a sequence which converges to the solution is proposed