Published December 2024 | Published
Journal Article

A Fast Algorithm for All-Pairs-Shortest-Paths Suitable for Neural Networks

  • 1. ROR icon California Institute of Technology

Abstract

Given a directed graph of nodes and edges connecting them, a common problem is to find the shortest path between any two nodes. Here we show that the shortest path distances can be found by a simple matrix inversion: if the edges are given by the adjacency matrix Aij, then with a suitably small value of γ, the shortest path distances are Dij = ceil(logγ[(I-γA)⁻¹]ij).We derive several graph-theoretic bounds on the value of γ and explore its useful range with numerics on different graph types. Even when the distance function is not globally accurate across the entire graph, it still works locally to instruct pursuit of the shortest path. In this mode, it also extends to weighted graphs with positive edge weights. For a wide range of dense graphs, this distance function is computationally faster than the best available alternative. Finally, we show that this method leads naturally to a neural network solution of the all-pairs-shortest-path problem.

Copyright and License

© 2024 Massachusetts Institute of Technology.

Acknowledgement

M.M. was supported by grants from the Simons Collaboration on the Global Brain (543015) and NIH (R01 NS111477). Thanks to Joel Tropp and Chris Umans for valuable feedback.

Code Availability

Code to produce the figures is available in a public repository: https://github.com/markusmeister/APSP.

Additional details

Created:
January 28, 2025
Modified:
January 28, 2025