Jing Zeyu, Meister Markus
Division of Biology and Biological Engineering California Institute of Technology.
ArXiv. 2024 Jul 24:arXiv:2308.07403v2.
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 then with a suitably small value of the shortest path distances are 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.
给定一个由节点和连接它们的边组成的有向图，一个常见的问题是找到任意两个节点之间的最短路径。在这里我们表明，最短路径距离可以通过一个简单的矩阵求逆来找到：如果边由邻接矩阵给出，那么对于一个适当小的 值，最短路径距离为 。我们推导了关于 值的几个图论界，并通过对不同类型图的数值计算来探索其有用范围。即使距离函数在整个图上不是全局准确的，它在局部仍然有效，可用于指导对最短路径的搜索。在这种模式下，它也适用于具有正边权重的加权图。对于广泛的稠密图，这个距离函数在计算上比现有的最佳替代方法更快。最后我们表明，这种方法自然地引出了全对最短路径问题的神经网络解决方案。
