The composition problem for shortest paths asks the following: given shortest paths on weighted graphs M and N which share a common boundary, find the shortest paths on their union. This problem is a crucial step in any algorithm which uses the divide and conquer method to find shortest paths. This extended abstract details how this problem may be understood categorically. Finding shortest paths is represented by a functor and the composition problem asks to find the value of this functor on a pushout using the values of the functor on the components. Furthermore, we present an algorithm which solves the composition problem for shortest paths. When implemented in Python, this algorithm reduces the computation time for finding shortest paths by relying on precompilation.
翻译：最短路径的构成问题要求如下: 在具有共同边界的加权图形 M 和 N 上找到最短路径, 找到最短路径 。 这个问题是使用分裂和征服方法寻找最短路径的任何算法的关键一步 。 此扩展的抽象细节如何明确理解这一问题 。 找到最短路径时由配方代表, 组成问题要求使用配方在组件上的配方值在推出时找到这个配方的价值 。 此外, 我们提出了一个算法, 解决最短路径的构成问题 。 在 Python 实施时, 此算法会减少使用预编算来找到最短路径的计算时间 。
相关内容
微信扫码咨询专知VIP会员