06年《程序员》有一期专题策划叫做”算法的力量”，被认为是年度最佳的一个专题，最近又温习一遍，重读李开复、凌小宁等人的文章，有不少新的收获。王咏刚那篇《算法悖论》提到斯坦福博士生Amit关于路径搜索的总结，简单读后感觉该学的东西还有很多。
一般说来，最短路算法划分为静态最短路和动态最短路算法。静态路径最短路是外界条件不变，计算起点到终点的最短路径，主要有Dijkstra算法和A*算法。而动态路径最短路是外界环境不断发生变化，无法计算预测路径的情况下求最短路，典型的有D*算法，在机器人探路中常应用D*算法，美国火星探测器的关键寻路算法就是采用的D*实现。其中自己更感兴趣以A*为代表的启发式路径搜索算法。
Dijkstra是数据结构中必定会涉及的典型最短路算法，Dijkstra算法按路径长度递增顺序产生一个节点到其他所有节点最短路径，以起始点为中心向外层层扩展，直到终点为止。Dijkstra算法可以得到最短路径的最优解，但由遍历计算的节点过多而效率较低。
启发式(Heuristic)A*(A-Star)算法应该是静态路网中求解最短路时最有效的方法。启发式搜索与深度优先(DFS)和广度优先(BFS)这类盲目型搜索最大的不同，在于当前搜索结点选择下一步路径时，通过启发函数计算选择代价最少的结点，设计优秀的启发函数往往求得最优解的同时具备较低的时间复杂度。而DFS和BFS算法在运气不好时可能需要遍历完整个解空间。
A*算法公式表示为：F(n)=G(n)+H(n)，其中F(n) 是节点n从初始点到目标点的估价函数，G(n) 是状态空间中从初始节点到n节点的实际代价，H(n)则是节点n到目标节点最佳路径的估计代价。当前结点到目标结点的估值函数H(n)是启发式搜索设计的核心。保证找到最短路径的充要条件是，估价函数H(n)计算的两点间距离小于等于实际距离。对于几何路网来说，可以取两节点间欧几理德直线距离做为估价值，即F(n)=G(n)+Sqrt((dx-nx)*(dx-nx)+(dy-ny) *(dy-ny))，这样估价函数F在G值一定的情况下，受估价值H制约保证路径搜索向终点的方向进行，而不是像Dijstra算法无方向的向四周延伸搜索。
最短路算法不仅在GIS的交通路线导航、路径分析领域应用广泛，在解决路径搜索相关的应用中也十分普遍，包括网络路由算法、机器人探路、人工智能、游戏设计等等。已有同学基于云风的路径搜索算法给出改进后的源代码，希望可以在理解A*算法原理方面提供一定帮助。
