什么算法计算地图上从 A 点到 B 点的方向？
地图提供商（例如 Google 或 Yahoo! Maps）如何建议路线？
我的意思是，他们可能拥有某种形式的真实世界数据，当然包括距离，但也可能包括行驶速度、人行道的存在、火车时刻表等。但假设数据采用更简单的格式，比如一个非常大的有向图边权重反映距离。 我希望能够快速计算从一个任意点到另一点的方向。 有时这些点会很接近（在一个城市内），有时会相距很远（跨国）。
像 Dijkstra 算法这样的图算法将不起作用，因为图很大。 幸运的是，像 A* 这样的启发式算法可能会起作用。 然而，我们的数据是非常结构化的，也许某种分层方法可能有效？ （例如，存储某些相距较远的“关键”点之间的预先计算的方向，以及一些局部方向。那么两个远处点的方向将涉及到一个关键点的局部方向，到另一个关键点的全局方向，然后是局部方向再次指示。）
在实践中实际使用了哪些算法？
附言。 这个问题的动机是发现在线地图方向的怪癖。 与三角不等式相反，有时 Google 地图认为 XZ 比 XYZ。 但也许他们的行走方向也针对另一个参数进行优化？
聚苯硫醚。 这是对三角不等式的另一个违反，这表明（对我来说）他们使用某种分层方法：XZ 与 XYZ。 前者似乎使用著名的塞瓦斯托波尔大道，尽管它有点偏僻。
编辑：这些示例似乎都不再起作用，但在原始帖子发布时都起作用了。
How do map providers (such as Google or Yahoo! Maps) suggest directions?
I mean, they probably have real-world data in some form, certainly including distances but also perhaps things like driving speeds, presence of sidewalks, train schedules, etc. But suppose the data were in a simpler format, say a very large directed graph with edge weights reflecting distances. I want to be able to quickly compute directions from one arbitrary point to another. Sometimes these points will be close together (within one city) while sometimes they will be far apart (cross-country).
Graph algorithms like Dijkstra's algorithm will not work because the graph is enormous. Luckily, heuristic algorithms like A* will probably work. However, our data is very structured, and perhaps some kind of tiered approach might work? (For example, store precomputed directions between certain "key" points far apart, as well as some local directions. Then directions for two far-away points will involve local directions to a key points, global directions to another key point, and then local directions again.)
What algorithms are actually used in practice?
PS. This question was motivated by finding quirks in online mapping directions. Contrary to the triangle inequality, sometimes Google Maps thinks that X-Z takes longer and is farther than using an intermediate point as in X-Y-Z. But maybe their walking directions optimize for another parameter, too?
PPS. Here's another violation of the triangle inequality that suggests (to me) that they use some kind of tiered approach: X-Z versus X-Y-Z. The former seems to use prominent Boulevard de Sebastopol even though it's slightly out of the way.
Edit: Neither of these examples seem to work anymore, but both did at the time of the original post.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（18）
作为一个在地图公司工作了 18 个月（其中包括研究路由算法的人）的人来说……是的，Dijkstra 的 确实有效，只需进行一些修改：
通过这些修改，您甚至可以在非常合理的时间内完成越野路线。
Speaking as someone who spent 18 months working at a mapping company, which included working on the routing algorithm... yes, Dijkstra's does work, with a couple of modifications:
With modifications along those lines, you can do even cross-country routing in a very reasonable timeframe.
这个问题近年来一直是一个活跃的研究领域。 主要思想是对图表进行预处理一次，以加速所有后续查询。 有了这些附加信息，可以非常快速地计算行程。 尽管如此，Dijkstra 算法仍然是所有优化的基础。
Arachnid描述了基于分层信息的双向搜索和边缘修剪的使用。 这些加速技术效果很好，但最新的算法无论如何都优于这些技术。 使用当前的算法，可以在大陆道路网络上以远小于一毫秒的时间计算出最短路径。 快速实现未修改的 Dijkstra 算法大约需要10 秒。
工程快速路线规划算法一文概述了这方面的研究进展场地。 有关更多信息，请参阅该论文的参考文献。
最快的已知算法不使用有关数据中道路的分层状态的信息，即它是高速公路还是地方道路。 相反，他们在预处理步骤中计算一个自己的层次结构，该层次结构经过优化以加快路线规划。 然后可以使用此预计算来修剪搜索：在 Dijkstra 算法中不需要考虑远离起点和目的地的慢速道路。 这样做的好处是非常好的性能和结果的正确性保证。
第一个优化的路线规划算法仅处理静态道路网络，这意味着图中的边具有固定的成本值。 这在实践中并非如此，因为我们想要考虑交通拥堵或车辆相关限制等动态信息。 最新的算法也可以处理此类问题，但仍有问题需要解决，研究正在进行中。
如果您需要最短路径距离来计算 TSP 的解决方案，那么您可能会对包含源和目的地之间的所有距离的矩阵感兴趣。 为此，您可以考虑使用高速公路层次结构计算多对多最短路径。 请注意，过去两年中更新的方法对此进行了改进。
This question has been an active area of research in the last years. The main idea is to do a preprocessing on the graph once, to speed up all following queries. With this additional information itineraries can be computed very fast. Still, Dijkstra's Algorithm is the basis for all optimisations.
Arachnid described the usage of bidirectional search and edge pruning based on hierarchical information. These speedup techniques work quite well, but the most recent algorithms outperform these techniques by all means. With current algorithms a shortest paths can be computed in considerable less time than one millisecond on a continental road network. A fast implementation of the unmodified algorithm of Dijkstra needs about 10 seconds.
The article Engineering Fast Route Planning Algorithms gives an overview of the progress of research in that field. See the references of that paper for further information.
The fastest known algorithms do not use information about the hierarchical status of the road in the data, i.e. if it is a highway or a local road. Instead, they compute in a preprocessing step an own hierarchy that optimised to speed up route planning. This precomputation can then be used to prune the search: Far away from start and destination slow roads need not be considered during Dijkstra's Algorithm. The benefits are very good performance and a correctness guarantee for the result.
The first optimised route planning algorithms dealt only with static road networks, that means an edge in the graph has a fixed cost value. This not true in practice, since we want to take dynamic information like traffic jams or vehicle dependent restrictrions into account. Latest algorithms can also deal with such issues, but there are still problems to solve and the research is going on.
If you need the shortest path distances to compute a solution for the TSP, then you are probably interested in matrices that contain all distances between your sources and destinations. For this you could consider Computing Many-to-Many Shortest Paths Using Highway Hierarchies. Note, that this has been improved by newer approaches in the last 2 years.
只是解决三角不等式违规问题，希望他们优化的额外因素是常识。 您不一定想要最短或最快的路线，因为它可能会导致混乱 和 破坏。 如果您希望您的路线选择对卡车友好的主要路线，并且可以应对每个卫星导航跟随的司机发送的情况，那么您很快就会放弃三角不等式[1]。
如果 Y 是 X 和 Z 之间的一条狭窄的住宅街道，则您可能只想在用户明确要求 XYZ 时使用通过 Y 的快捷方式。 如果他们要求 XZ，他们应该坚持走主要道路，即使有点远并且需要更长的时间。 它类似于 Braess 悖论 - 如果每个人都试图走最短、最快的路线，那么由此产生的拥堵意味着这不再是任何人的最快路线。 从这里我们就从图论转向了博弈论。
[1] 事实上，当您允许单向道路并失去对称性要求时，任何所产生的距离将是数学意义上的距离函数的希望都会消失。 失去三角不等式无异于在伤口上撒盐。
Just addressing the triangle inequality violations, hopefully the extra factor they're optimising for is common sense. You don't necessarily want the shortest or fastest route, as it can lead to chaos and destruction. If you want your directions to prefer the major routes that are truck-friendly and can cope with having every sat-nav-following driver sent down them, you quickly discard the triangle inequality[1].
If Y is a narrow residential street between X and Z, you probably do only want to use the shortcut via Y if the user explicitly asks for X-Y-Z. If they ask for X-Z, they should stick to major roads even if it's a bit further and takes a bit longer. It's similar to Braess's paradox - if everyone tries to take the shortest, fastest route, the resulting congestion means that it's not the fastest route for anyone any more. From here we stray from graph theory into game theory.
[1] In fact, any hope that the distances produced will be a distance function in the mathematical sense dies when you allow one-way roads and lose the symmetry requirement. Losing the triangle inequality too is just rubbing salt in the wound.
以下是对世界上最快的路由算法进行比较并证明其正确性：
http://algo2.iti .uka.de/schultes/hwy/schultes_diss.pdf
这是关于该主题的 Google 技术讲座：
http://www.youtube.com/watch?v=-0ErpE8tQbw
这是 schultes 讨论的高速公路层次结构算法的实现（目前仅在柏林，我正在编写接口和移动版本也在开发中）：
http://tom.mapsforge.org/
Here's the world's fastest routing algorithms compared and proven for correctness:
http://algo2.iti.uka.de/schultes/hwy/schultes_diss.pdf
Here's a google tech talk on the subject:
http://www.youtube.com/watch?v=-0ErpE8tQbw
Here's a implementation of the highway-hierarchies algorithm as discussed by schultes (currently in berlin only, I'm writing the interface and a mobile version is being developed as well):
http://tom.mapsforge.org/
就静态道路网络的查询时间而言，当前最先进的算法是 Abraham 等人提出的 Hub 标记算法。 http://link.springer.com/chapter/10.1007/978-3-642- 20662-7_20。 最近以 Microsoft 技术报告的形式发布了对该领域的全面且出色的调查http://research.microsoft.com/pubs/207102/MSR-TR-2014-4.pdf">http:// /research.microsoft.com/pubs/207102/MSR-TR-2014-4.pdf。
简短的版本是...
Hub 标记算法为静态道路网络提供最快的查询，但需要大量 RAM 才能运行 (18 GiB)。
尽管传输节点路由稍微慢一些，但它只需要大约 2 GiB 的内存，并且预处理时间更快。
收缩层次结构在快速预处理时间、低空间要求 (0.4 GiB) 和快速查询时间之间提供了良好的权衡。
没有一种算法能够完全占据主导地位...
Peter Sanders 的 Google 技术演讲可能会引起您的兴趣
https://www.youtube .com/watch?v=-0ErpE8tQbw
还有 Andrew Goldberg 的演讲
https://www.youtube.com /watch?v=WPrkc78XLhw
收缩层次结构的开源实现可从 KIT 的 Peter Sanders 研究小组网站获得。 http://algo2.iti.kit.edu/english/routeplanning.php
也是一个易于访问的博客Microsoft 撰写的有关 CRP 算法用法的帖子... http ://blogs.bing.com/maps/2012/01/05/bing-maps-new-routing-engine/
The current state of the art in terms of query times for static road networks is the Hub labelling algorithm proposed by Abraham et al. http://link.springer.com/chapter/10.1007/978-3-642-20662-7_20 . A through and excellently written survey of the field was recently published as a Microsoft technical report http://research.microsoft.com/pubs/207102/MSR-TR-2014-4.pdf .
The short version is...
The Hub labelling algorithm provides the fastest queries for static road networks but requires a large amount of ram to run (18 GiB).
Transit node routing is slightly slower, although, it only requires around 2 GiB of memory and has a quicker preprocessing time.
Contraction Hierarchies provide a nice trade off between quick preprocessing times, low space requirements (0.4 GiB) and fast query times.
No one algorithm is completely dominate...
This Google tech talk by Peter Sanders may be of interest
https://www.youtube.com/watch?v=-0ErpE8tQbw
Also this talk by Andrew Goldberg
https://www.youtube.com/watch?v=WPrkc78XLhw
An open source implementation of contraction hierarchies is available from Peter Sanders research group website at KIT. http://algo2.iti.kit.edu/english/routeplanning.php
Also an easily accessible blog post written by Microsoft on there usage of the CRP algorithm... http://blogs.bing.com/maps/2012/01/05/bing-maps-new-routing-engine/
我以前没有在谷歌、微软或雅虎地图上工作过，所以我无法告诉你它们是如何工作的。
然而，我确实为一家能源公司设计了一个定制的供应链优化系统，其中包括为其卡车车队提供调度和路线应用程序。 然而，我们的路线选择标准远比建筑、交通放缓或车道封闭的情况更具业务针对性。
我们采用了一种称为 ACO（蚁群优化）的技术来调度和路线卡车。 该技术是一种应用于旅行商问题以解决路径问题的人工智能技术。 ACO 的技巧是根据已知的路由事实构建错误计算，以便图解模型知道何时退出（何时错误足够小）。
您可以通过 google 搜索 ACO 或 TSP 来找到有关此技术的更多信息。 然而，我没有为此使用过任何开源人工智能工具，因此无法推荐一个（尽管我听说 SWARM 非常全面）。
I've not worked on Google or Microsoft or Yahoo Maps before, so I can't tell you how they work.
However, I did architect a custom supply chain optimization system for an energy company which included a scheduling and routing application for their fleet of trucks. However, our criteria on routing was far more business-specific than where is construction or traffic slows or lane closures.
We employed a technique called ACO (Ant colony optimization) to schedule and route trucks. This technique is an AI technique that was applied to the traveling salesman problem to solve routing problems. The trick with ACO is to build an error calculation based upon known facts of the routing so that the graph solving model knows when to quit (when is the error small enough).
You can google ACO or TSP to find more on this technique. I've not used any of the open-source AI tools for this however, so cannot suggest one (though I heard SWARM was pretty comprehensive).
这个论点不一定成立，因为 Dijkstra 通常不会查看完整的图，而只会查看一个非常小的子集（图互连得越好，该子集越小）。
对于表现良好的图，Dijkstra 实际上可能表现得相当好。 另一方面，通过仔细的参数化，A* 将始终表现得一样好，甚至更好。 您是否已经尝试过它如何处理您的数据？
也就是说，我也很想听听其他人的经历。 当然，像谷歌地图搜索这样的突出例子特别有趣。 我可以想象类似有向最近邻启发式的东西。
This argument doesn't necessarily hold because Dijkstra will not usually look at the complete graph but rather just a very small subset (the better interconnected the graph, the smaller this subset).
Dijkstra may actually perform rather well for well-behaved graphs. On the other hand, with careful parametrization A* will always perform just as good, or better. Have you already tried how it would perform on your data?
That said, I'd also be very interested to hear about other peoples' experiences. Of course, prominent examples like Google Map's search are particularly interesting. I could imagine something like a directed nearest neighbour heuristic.
我有点惊讶没有看到这里提到的 Floyd Warshall 算法。 该算法的工作原理非常类似于 Dijkstra 的算法。 它还有一个非常好的功能，那就是只要您愿意继续允许更多中间顶点，它就允许您进行计算。 因此，它自然会相当快地找到使用州际公路或高速公路的路线。
I am a little suprised to not see Floyd Warshall's algorithm mentioned here. This algorithm work's very much like Dijkstra's. It also has one very nice feature which is it allows you to compute as long as you would like to continue allowing more intermediate vertices. So it will naturally find the routes which use interstates or highways fairly quickly.
事实上，我已经这样做了很多次，尝试了几种不同的方法。 根据地图的大小（地理），您可能需要考虑使用半正矢函数作为启发式方法。
我做出的最佳解决方案是使用 A* 和直线距离作为启发式函数。 但是，您需要地图上每个点（交叉点或顶点）的某种坐标。 您还可以尝试启发式函数的不同权重，即
其中 k 是大于 0 的某个常数。
I've done this quite a lot of times, actually, trying several different methods. Depending on the size (geographical) of the map, you might want to consider using the haversine function as a heuristic.
The best solution I've made was using A* with a straight line distance as a heuristic function. But then you need some sort of coordinates for each point (intersection or vertex) on the map. You can also try different weightings for the heuristic function, i.e.
where k is some constant greater than 0.
可能类似于主要地点和分层地图之间预先计算的路线的答案，但我的理解是，在游戏中，为了加速 A*，你有一个对于宏观导航来说非常粗糙的地图，以及一个对于导航到宏观方向的边界。 所以你有 2 条小路径需要计算，因此你的搜索空间比简单地计算一条到达目的地的路径要小得多。 如果您经常这样做，您就会有大量预先计算的数据，因此至少部分搜索是搜索预先计算的数据，而不是搜索路径。
Probably similar to the answer on pre-computed routes between major locations and layered maps, but my understanding is that in games, to speed up A*, you have a map that is very coarse for macro navigation, and a fine-grained map for navigation to the boundary of macro directions. So you have 2 small paths to calculate, and hence your search space is much much smaller than simply doing a single path to the destination. And if you're in the business of doing this a lot, you'd have a lot of that data pre-computed so at least part of the search is a search for pre-computed data, rather than a search for a path.
这纯粹是我的猜测，但我认为他们可能会使用覆盖有向图的影响图数据结构来缩小搜索范围。 当所需行程较长时，这将使搜索算法能够将路径引导至主要路线。
鉴于这是一个 Google 应用程序，因此可以合理地假设很多魔力都是通过广泛的缓存完成的。 :) 如果缓存前 5% 最常见的 Google 地图路线请求允许通过简单的查找来回答大块（20%？50%？）的请求，我不会感到惊讶。
This is pure speculation on my part, but I suppose that they may use an influence map data structure overlaying the directed map in order to narrow the search domain. This would allow the search algorithm to direct the path to major routes when the desired trip is long.
Given that this is a Google app, it's also reasonable to suppose that a lot of the magic is done via extensive caching. :) I wouldn't be surprised if caching the top 5% most common Google Map route requests allowed for a large chunk (20%? 50%?) of requests to be answered by a simple look-up.
我对此有更多的想法：
1）记住地图代表一个物理组织。 存储每个交叉路口的纬度/经度。 除了目标方向上的点之外，您不需要检查太多内容。 只有当你发现自己受阻时，你才需要超越这一点。 如果您存储了高级连接的覆盖层，您可以进一步限制它 - 通常您永远不会以偏离最终目的地的方式遇到其中一个。
2）将世界划分为由有限连接定义的一大堆区域，定义区域之间的所有连接点。 查找您的源和目标所在的区域、从您所在位置到每个连接点的起始区域和结束区域路线、以及连接点之间的简单地图之间的区域。 （我怀疑后者的很多内容已经预先计算过了。）
请注意，区域可能比大都市区还要小。 任何具有将其划分的地形特征（例如河流）的城市都将是多个区域。
I had some more thoughts on this:
1) Remember that maps represent a physical organization. Store the latitude/longitude of every intersection. You don't need to check much beyond the points that lie in the direction of your target. Only if you find yourself blocked do you need to go beyond this. If you store an overlay of superior connections you can limit it even more--you will normally never go across one of those in a way that goes away from your final destination.
2) Divide up the world into a whole bunch of zones defined by limited connectivity, define all connectivity points between the zones. Find what zones your source and target are in, for the start and end zone route from your location to each connection point, for the zones between simply map between connection points. (I suspect a lot of the latter is already pre-calculated.)
Note that zones can be smaller than a metropolitan area. Any city with terrain features that divide it up (say, a river) would be multiple zones.
我对所使用的启发法非常好奇，不久前我们得到了从圣罗莎附近的同一起始位置到优胜美地国家公园的两个不同露营地的路线。 这些不同的目的地产生了截然不同的路线（通过 I-580 或 CA-12），尽管事实上两条路线在最后 100 英里（沿着 CA-120）汇合，然后在最后再次分叉了几英里。 这是相当可重复的。 两条路线相距 50 英里，总里程约为 100 英里，但正如您所期望的，距离/时间非常接近。
唉，我无法重现这一点 - 算法一定已经改变了。 但这让我对算法感到好奇。 我所能推测的是，存在一些方向修剪，它恰好对从远处看到的目的地之间的微小角度差异非常敏感，或者根据最终目的地的选择选择了不同的预先计算的分段。
I was very curious about the heuristics used, when a while back we got routes from the same starting location near Santa Rosa, to two different campgrounds in Yosemite National Park. These different destinations produced quite different routes (via I-580 or CA-12) despite the fact that both routes converged for the last 100 miles (along CA-120) before diverging again by a few miles at the end. This was quite repeatable. The two routes were up to 50 miles apart for around 100 miles, but the distances/times were pretty close to each other as you would expect.
Alas I cannot reproduce that - the algorithms must have changed. But it had me curious about the algorithm. All I can speculate is that there was some directional pruning which happened to be exquisitely sensitive to the tiny angular difference between the destinations as seen from far away, or there were different precomputed segments selected by the choice of final destination.
说到 GraphHopper，
一个基于OpenStreetMap的快速开源路线规划器，我阅读了一些文献并实现了一些方法。 最简单的解决方案是 Dijkstra，一个简单的改进是双向 Dijkstra，它大约只探索一半的节点。 使用双向 Dijkstra，穿越整个德国的路线已经需要 1 秒（对于汽车模式），在 C 语言中可能只需要 0.5 秒左右；）
我用双向 Dijkstra 创建了一个真实路径搜索的动画 gif 此处。 还有一些更多的想法让 Dijkstra 更快 就像做A*，这是一个“目标导向的Dijkstra”。 我还为其创建了一个 gif 动画。
但是如何更快地做到这一点？
问题是，对于路径搜索，必须探索位置之间的所有节点，这确实成本高昂，因为在德国已经有数百万个节点。 但 Dijkstra 等的另一个痛点是此类搜索使用大量 RAM。
有启发式解决方案，也有将图（道路网络）分层组织的精确解决方案，两者都有优点和缺点，主要解决速度和 RAM 问题。 我在这个答案中列出了其中一些。
对于 GraphHopper，我决定使用 收缩层次结构 因为它相对“容易”实现，并且不准备图表需要很长时间。 它仍然会导致非常快的响应时间，就像您可以在我们的在线实例 GraphHopper 地图 上进行测试一样。 例如从南非飞往中国东部 这导致汽车行驶了 23000 公里的距离和近 14 天的行驶时间，并且在服务器上仅花费了约 0.1 秒。
Speaking of GraphHopper,
a fast Open Source route planner based on OpenStreetMap, I have read a bit literature and implemented some methods. The simplest solution is a Dijkstra and a simple improvement is a bidirectional Dijkstra which explores roughly only the half of the nodes. With bidirctional Dijkstra a route through entire Germany takes already 1sec (for car mode), in C it would be probably only 0.5s or so ;)
I've created an animated gif of a real path search with bidirectional Dijkstra here. Also there are some more ideas to make Dijkstra faster like doing A*, which is a "goal-oriented Dijkstra". Also I've create a gif-animation for it.
But how to do it (a lot) faster?
The problem is that for a path search all nodes between the locations have to be explored and this is really costly as already in Germany there are several millions of them. But an additional pain point of Dijkstra etc is that such searches uses lots of RAM.
There are heuristic solutions but also exact solutions which organzize the graph (road network) in hierarchical layers, both have pro&cons and mainly solve the speed and RAM problem. I've listed some of them in this answer.
For GraphHopper I decided to use Contraction Hierarchies because it is relative 'easy' to implement and does not take ages for preparation of the graph. It still results in very fast response times like you can test at our online instance GraphHopper Maps. E.g. from south Africa to east China which results in a 23000km distance and nearly 14 days driving time for car and took only ~0.1s on the server.
我在路由方面工作了几年，最近由于客户的需求而进行了大量的活动，我发现 A* 很容易足够快； 确实没有必要寻找优化或更复杂的算法。 在巨大的图上进行路由不是问题。
但速度取决于整个路由网络，我指的是内存中分别代表路由段和交叉点的弧线和节点的有向图。 主要的时间开销是创建这个网络所花费的时间。 一些粗略数据基于运行 Windows 的普通笔记本电脑，并在整个西班牙进行路由：创建网络所需的时间：10-15 秒； 计算路线所需的时间：太短，无法测量。
另一件重要的事情是能够重复使用网络来进行任意数量的路由计算。 如果您的算法以某种方式标记节点以记录最佳路线（到当前节点的总成本及其最佳弧线） - 正如 A* 中所必须的 - 您必须重置或清除这些旧信息。 使用代号系统比经历数十万个节点更容易。 为每个节点标记其数据的代号； 计算新路线时增加生成编号； 任何具有较旧代号的节点都是陈旧的，其信息可以被忽略。
I have worked on routing for a few years, with a recent burst of activity prompted by the needs of my clients, and I've found that A* is easily fast enough; there is really no need to look for optimisations or more complex algorithms. Routing over an enormous graph is not a problem.
But the speed depends on having the entire routing network, by which I mean the directed graph of arcs and nodes representing route segments and junctions respectively, in memory. The main time overhead is the time taken to create this network. Some rough figures based on an ordinary laptop running Windows, and routing over the whole of Spain: time taken to create the network: 10-15 seconds; time taken to calculate a route: too short to measure.
The other important thing is to be able to re-use the network for as many routing calculations as you like. If your algorithm has marked the nodes in some way to record the best route (total cost to current node, and best arc to it) - as it has to in A* - you have to reset or clear out this old information. Rather than going through hundreds of thousands of nodes, it's easier to use a generation number system. Mark each node with the generation number of its data; increment the generation number when you calculate a new route; any node with an older generation number is stale and its information can be ignored.
我看到OP中的地图出了什么问题：
看看指定了中间点的路线：由于那条路不直，路线稍微向后走。
如果他们的算法不会回溯，它就不会看到更短的路线。
I see what's up with the maps in the OP:
Look at the route with the intermediate point specified: The route goes slightly backwards due to that road that isn't straight.
If their algorithm won't backtrack it won't see the shorter route.
全对最短路径算法将计算图中所有顶点之间的最短路径。 这将允许预先计算路径，而不是每次有人想要找到源和目的地之间的最短路径时都需要计算路径。 Floyd-Warshall 算法是一种全对最短路径算法。
An all-pairs shortest path algorithm will compute the shortest paths between all vertices in a graph. This will allow paths to be pre-computed instead of requiring a path to be calculated each time someone wants to find the shortest path between a source and a destination. The Floyd-Warshall algorithm is an all-pairs shortest path algorithm.
地图永远不会考虑整个地图。
我的猜测是：-
1. 根据您的位置，他们加载一个地点以及该地点上的地标。
2. 当您搜索目的地时，他们会加载地图的其他部分并从两个位置绘制图表，然后应用最短路径算法。
另外，还有一种重要的技术动态规划，我怀疑它被用于计算最短路径。 你也可以参考一下。
Maps never take into consideration the whole map.
My guess is:-
1. According to your location, they load a place and the landmarks on that place.
2. When you search the destination, thats when they load the other part of the map and make a graph out of two places and then apply the shortest path algorithms.
Also, there is an important technique Dynamic programming which i suspect is used in the calculation of shortest paths. You can refer to that as well.