An analog parallel distributed solution to the shortest path problem

The evolution of analog VLSI has led to increased application of analog circuitry in solving problems previously solved digitally or numerically. Specifically, analog parallel distributed (APD) methods have been used. These methods are applicable to problems that can be modeled using the mathematical functions characteristic of analog circuits. One such problem is the single-source shortest path problem (SPP). An SPP algorithm that is derived by applying an APD approach to solving Bellman´s equation is proposed. Correctness of the algorithm is proved for the case of zero-initial conditions. Simulations of the system (algorithm) yield correct results in all cases. A decomposition technique is developed to analyze the dynamic behavior of the algorithm in detail. The complexity, accuracy, and settling time of a physical implementation of the system are also discussed