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

Question

8

我最近一直在使用OSRM路由库。它似乎非常高效地解决了最短路径问题。然而，我没有看到如何使用它来计算单源最短路径。更准确地说，给定一个固定的起点，计算到所有可以在给定距离限制内到达的位置的最短距离（例如，在30分钟内可到达）。

OSRM在内部使用收缩分层技术。据我所知，当涉及到计算实际数据中两个位置之间的距离时，这种技术比Dijkstra算法要优越得多。然而，对于我的问题，Dijkstra算法似乎更适合，不是吗？

OSRM是否提供API来计算单源最短路径问题（带有距离限制）？还有其他更适合此类问题的免费路由库吗？最好支持OpenStreetMap数据。

- Philipp Claßen

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Karussell · Accepted Answer

OSRM使用缩写层次（CH）来实现“一对一路由”的快速。为了使CH工作，您需要一个适应性双向算法（A*，Dijkstra等），因此单源情况更加困难。但是，如果您事先知道要到达哪些目的地，则“一对多”算法相对简单。

此外，如果您想要一个“非目标导向的双向搜索”解决方案，该方案使用查找表，请参阅论文“Fast Detour Computation for Ride Sharing”或此处。

其他免费的路由库？

我建议使用我的Java GraphHopper项目 ;)