Bound Smoothing

Input distances usually define only a small fraction of the interatomic distances in the system. However, they do imply upper and lower bounds on the other atoms to which they are connected by means of the triangle inequalities (Crippen and Havel, 1988). Determining these implied bounds is equivalent to a well-studied computational problem, finding the shortest path between two points in a directed graph. The shortest-path algorithm used in this implementation is that of Dijkstra (see Tarjan (1983) for a review). It proceeds by calculating the shortest paths from one atom (the root) to all other atoms. The shortest-path routine calculates both upper and lower bounds by keeping track of two halves of the graph, one that holds the upper bounds and one that holds the lower. By solving the shortest-path problem for the upper bounds first, the program can then calculate the lower bounds by continuing the shortest-path routine with the second half of the graph. This process is repeated, with each atom taking its turn as root.