最经济路线规划算法研究

An Algorithm of Cheapest Bus Route Planning

在城市的公交网络系统中,如果通过乘公交车从点X到点Y,那么如何乘坐(可能需要换乘公交车),使得花费最少?这是Datar和Ranade提出的一个开问题。该文通过对城市公交网络系统的分析,给出了一个解决该问题的时间复杂度为多项式的算法。另外文章还讨论了当找到一条费用最小的乘车路线规划时,如何乘坐公交车使得能最快地到达目的地,并给出了时间复杂度为多项式的算法。

In the bus network of a city,what is the cheapest way from point X to point Y with bus changes as necessary?This is an open question posed by Datar and Ranade.We present a polynomial algorithm to solve it.After a cheapest way is found,we give another algorithm to get the fastest way from the source point to the destination point with the cheapest cost.