关于最短路径算法，很多人会首先考虑Dijkstra算法。
这里介绍灵活的最短路径搜索的算法——双向A*。
先从A*算法开始吧。
*算法是一种启发式搜索算法，通过对周边节点进行评估，进行下一步搜索，直到得到最优节点到达目标节点，可以大大减少无恐惧搜索路径，提高搜索效率。
电子游戏中最主要的应用是寻找地图上两点之间的最佳路线。
*的核心算法公式为F=G H。
g是从起点到当前节点的代价，h是从当前节点到目标节点的代价。
传球
在图中，红色节点是起点，蓝色节点是目标节点。
*算法首先计算从起点到起点周边的8个节点的成本，以及从该节点到目的地节点的成本，从中选择最佳节点，同样计算直到到达目的地节点。
传球
双向A*算法从起点和终点分别进行A*搜索，直到他们搜索到的节点重复为止。
这样，在节点复杂的情况下，通过双向搜索可以大大减少路径搜索过程中检查的节点数量。
此时，考虑一下使用双向A*算法实现简单公交换乘的算法。
首先，将某城市公交线路的站点、站点数据组织成站点和站点的一对多数据结构。
1、根据起始位置找到附近n米站台。
2、根据终点位置找到附近n米站台。
3、根据起点附近的站台，找到通过这些站台的所有线路集合a。
4、找到所有从起点出发的换乘一次的路线集合b。
5、根据终点附近的站台，找到到达这些站台的所有线路集合c。
6、找到到达终点站的所有换乘路线的集合d。
7、A和C的交叉点为直通线路。
8、A和D交叉为一次换乘路线。
9、B和C的交点是换乘路线。
10、B和D交叉为二次换乘线路。
获得换乘结果后，可以根据需求，找到最佳换乘路线的集合。