A new O(n2) shortest chain algorithm

摘要

A new shortest chain algorithm is developed for finding shortest or longest chains from one node to all other nodes in a connected network. The network is first transformed into a directed network. The algorithm constructs an acyclic auxiliary shortest (longest) chain network from the directed network, using the concepts of minimum cost and remaining degree of nodes in an attempt to make several “parallel” decisions at each step. The twofold decision process causes faster convergence to the optimum solution than with a version of the algorithm using only the minimum cumulative cost criteria, or with node labeling techniques. The algorithm works on networks with all cost coefficients either nonnegative or nonpositive, i.e., mixed costs are not allowed.