Title :
Solving the shortest path problem using an analog network
Author :
Bu, Linkai ; Chiueh, Tzi-Dar
Author_Institution :
Dept. of Electr. Eng., Nat. Taiwan Univ., Taipei, Taiwan
fDate :
11/1/1999 12:00:00 AM
Abstract :
The shortest path problem is one of the most important combinatorial optimization problems. In this paper, a network consisting of variable turn-on-voltage diodes (VTDs) is proposed for tackling the shortest path problem. The network solves the shortest path problem in a parallel and distributed manner. The network itself is isomorphic to the graph in which the shortest path solution is to be sought. The proposed VTD network settles to steady-state solutions quickly and consumes very little power. It is also shown theoretically that the VTD network solves the shortest path problem exactly. A circuit implementation of the VTD network is proposed and simulation results confirm its functionality. Finally, two physical limitations of VTD´s and their effect on the performance are discussed
Keywords :
analogue circuits; circuit optimisation; graph theory; network topology; analog network; circuit implementation; combinatorial optimization problems; graph theory; physical limitations; shortest path problem; simulation results; steady-state solutions; variable turn-on-voltage diodes; Circuit simulation; Concurrent computing; Diodes; Energy consumption; Hardware; Large-scale systems; Neural networks; Optimization methods; Shortest path problem; Steady-state;
Journal_Title :
Circuits and Systems I: Fundamental Theory and Applications, IEEE Transactions on