algorithm - 我如何计算通过可选航路点从起点到目的地的 map 路线？

Question

假设我想绘制一条从旧金山到纽约的导航路线。大约有 1000 种服务可以免费执行此操作。还有许多服务可以解决旅行商问题并计算通过 6 个城市的路线，找出最佳顺序。这些都是解决的问题。

现在假设我想绘制一条从 SF 到 NY 的路线，沿途停在数据库中的 EV 充电器处。

这比一堆路标更难，因为我不需要在每个路标处都停下来。我只需要限制我的路线从一个跳到下一个。

我该如何解决这个问题？有没有我可以用来简化这个的算法？或者我可以使用 OSRM ( https://github.com/Project-OSRM/osrm-backend ) 以某种方式帮助我，而不是依赖公共(public) API。我们可以暴力破解它并继续计算路线，直到我们找到最短的路线，但我可以看到它很快就会崩溃。

Answer 1

构造一个有向图。路点是节点，如果充满电的汽车可以覆盖该距离，则您可以在路点 A 和路点 B 之间放置一条有向加权边。然后您需要在加权有向图中找到最短路径。