论文标题
如何构成最短路径
How to Compose Shortest Paths
论文作者
论文摘要
最短路径的组成问题询问以下内容：在具有共同边界的加权图M和N上的最短路径，在其结合中找到最短路径。此问题是使用划分和征服方法找到最短路径的任何算法中的关键步骤。该扩展的抽象详细介绍了如何明确理解此问题。查找最短路径由函子表示，组成问题要求使用组件上的函子的值在定位上找到该函子的值。此外，我们提出了一种算法，该算法解决了最短路径的组成问题。在Python中实施时，该算法会减少通过依靠预兼容来找到最短路径的计算时间。
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.
