如何使用OSRM计算单源最短路径？

Question

我最近一直在使用OSRM路由库。它在解决最短路径问题上似乎非常有效。然而，我不知道如何用它来计算单源最短路径。更准确地说，在给定固定起点的情况下，计算在给定距离限制内可以到达的所有位置的最短距离(例如，30分钟内可到达)。

OSRM在内部使用收缩层次结构。据我所知，在计算现实世界数据中两个位置之间的距离时，这种技术比Dijkstra的算法要好得多。然而，对于我的问题，Dijkstra的算法似乎更适合，不是吗？

OSRM是否提供API来计算单源最短路径问题(对距离有限制)？有没有其他免费的路由库更适合这种类型的问题？最好是具有对OpenStreetMap数据的良好支持的一个。

Answer 1

OSRM正在使用收缩层次结构(CH)来实现“一对一路由”。为了让CH工作，你需要一个自适应的双向算法(A*，Dijkstra，...)因此，单一来源的情况更加困难。但是，如果你预先知道你想要哪个目的地，一对多算法是相对简单的。

如果你想要一个使用查找表的“非目标导向的双向搜索”的解决方案，也可以看看论文"Fast Detour Computation for Ride Sharing“或here。

其他免费的路由库？

我会推荐我的Java GraphHopper项目;)

当然还有更多：http://wiki.openstreetmap.org/wiki/Routing