s***y
发帖数: 3042 | 1 给定2点，找一条路。对于gps和google maps，都是用什么算法？shortest path吗？路
都是纵横交错，每个交叉路口，难道不是都要变成一个节点吗？如果这样，这个
network应该很大吧。这个算法怎么可以运行的很快？请教大家，这个该用什么算法，
什么数据结构比较好。 |
b*****c
发帖数: 1103 | |
B******5
发帖数: 4676 | 3 计算的也不快吧，GPS的说的最多的语言是Recalculating |
d*******3
发帖数: 6550 | 4 还要考虑到限速和traffic的问题，算的应该是时间最短的路线 |
s***y
发帖数: 3042 | 5 恩，这个应该是设weight的时候，按照时间来决定weight了吧。
【在 d*******3 的大作中提到】
: 还要考虑到限速和traffic的问题，算的应该是时间最短的路线
|
s***y
发帖数: 3042 | 6 谢谢了，刚刚找到一个说法，说现在最快的是用Dijkstra's shortest path algorithm
和fibonacci heap。为了缩短query的时间，有些会做preprocessing。不过是个
storage和computation的tradeoff。
【在 b*****c 的大作中提到】
: 不大不大，100万个路口都没问题
|
