Low-Complexity Method for Shortest Path Optimization Problems Based on Nanowire Memristor Network

The shortest path problem is a cornerstone in graph theory, with traditional algorithms often incurring a computational complexity of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathrm{O}\left(\mathrm{n}^{2}\right)$</tex>. In recent years, Ag nanowire memristor networks have emerged as a promising candidate for nextgeneration hardware due to their excellent random fullinterconnectivity and memristive properties. This work introduces a novel approach to implement the shortest path problem using Ag nanowire network hardware, which significantly reduces the computational complexity from <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathrm{O}\left(\mathrm{n}^{2}\right)$</tex> to <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathrm{O}(1)$</tex>, thereby enhancing computational efficiency dramatically. Our method not only offers a substantial improvement in performance but also paves the way for future algorithmic deployment on nanowire networks.