osrm - 为什么 OSRM 实施收缩层次结构和 MLD 而不是 A*？

Question

我正在经历 OSRM 的实施；他们实现了路由算法 CH 和 MLD。我想知道使用这些算法背后的动机。更重要的是，我们不能在这两种算法中动态改变边缘权重。

标签： osrm

Answer 1

在 OSRM 中实现的 CH 和 MLD 算法是“加速算法”——它们可以在增强图上更快地找到最短路径。

使用这些类型的算法的典型权衡是您失去了灵活性 - 增强图的形状取决于权重，因此如果您更改它们，您需要重新生成增强图以使其继续有效。