请教问题：gps和google maps背后的算法 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

请教问题：gps和google maps背后的算法

请教问题：gps和google maps背后的算法# JobHunting - 待字闺中

s*y2012-01-01 08:01

1 楼

给定2点，找一条路。对于gps和google maps，都是用什么算法？shortest path吗？路
都是纵横交错，每个交叉路口，难道不是都要变成一个节点吗？如果这样，这个
network应该很大吧。这个算法怎么可以运行的很快？请教大家，这个该用什么算法，
什么数据结构比较好。

b*c2012-01-01 08:01

2 楼

不大不大，100万个路口都没问题

B*52012-01-01 08:01

3 楼

计算的也不快吧，GPS的说的最多的语言是Recalculating

d*32012-01-01 08:01

4 楼

还要考虑到限速和traffic的问题，算的应该是时间最短的路线

s*y2012-01-01 08:01

5 楼

恩，这个应该是设weight的时候，按照时间来决定weight了吧。

【在 d*******3 的大作中提到】

: 还要考虑到限速和traffic的问题，算的应该是时间最短的路线

s*y2012-01-01 08:01

6 楼

谢谢了，刚刚找到一个说法，说现在最快的是用Dijkstra's shortest path algorithm
和fibonacci heap。为了缩短query的时间，有些会做preprocessing。不过是个
storage和computation的tradeoff。

【在 b*****c 的大作中提到】

: 不大不大，100万个路口都没问题