title: 公共交通线路的搜索是如何实现的？简称公交换乘算法
desc: 在地图搜索引擎出现之前，人们只能通过人工查询地图和询问熟悉当地交通的人士获得自己的出行路线。有了地图搜索引擎之后，大大减少了此类工作的劳动量。<br>1. 这种搜索的算法是如何实现的呢？<br>2. 如何在错综复杂的交通和地图数据中找到相对较优的解法的？<br>3. 有没有公开的或者开源的算法？<br>4. 如果是基于图论里面的计算最短路径的算法，那么实际应用中的复杂在哪些方面呢？
topic: 交通
content: 公交换乘搜索的基本思想就是将城市的公交换乘网络抽象为一张有向带权图，将用户输入的起终点转换为有向带权图中的起始节点s和终止节点t，然后搜索找到s，t之间的K条较优通路。公交搜索返回的方案一般都不止一条 至于如何在图中寻找K条较优通路，基本的算法有： 1. 广度优先搜索BFS出一堆的结果比如500条方案，然后对结果进行排序 2. 如果方案的优劣可以通过边权加和来衡量，那么亦可以用Dijkstra算法依次寻找K条短路 以上的
answerer_tags: Geo Hacker