A Polynomial Interval Shortest-Route Algorithm for Acyclic Network
Hossain M. Akter · 2012
A method and algorithm is presented for solving the shortest-route problem. New algorithm is applicable to the case when the generalized length (distance, cost, time, etc.) associated with each arc is nonnegative, interval or real. An interval algorithm is developed on the base of midpoint and half-width representation of intervals and the new algorithm is more efficient than the interval algorithm that could be proposed by using traditional interval description. The complexity of the new algorithm is evaluated.