文章编号：1672-5328（2012）06-0086-04

郑健琛¹，陈建宇¹，龙燕君²
（1.西南交通大学交通运输与物流学院，四川 成都 610031；2. 西南交通大学艺术与传播学院，四川 成都 610031）

摘要：为研究乘客使用公共交通的实际出行距离，基于公交复杂网络中的换乘网络Space P拓扑结构，结合公交车站的经纬度坐标，建立以距离为边权的加权公交换乘网络。基于该加权网络，设计了综合考虑换乘次数和路径长度的最短路算法，该算法可保证在站间换乘次数最少的基础上通过的路径也相对最短。利用成都市公交网络进行实例分析，并与Floyd算法进行对比，结果显示，由该算法得到的平均最短路径长度增加3.7 km，但平均换乘次数下降0.64次，更符合乘客的出行习惯；随机选择一些车站进行最优换乘路径选取试验，结果表明，由该算法得到的方案在保证换乘次数最少基础上，得到的路径也基本最短，证明了算法的有效性。

关键词：复杂网络；公交换乘；最短路算法；距离加权

中图分类号：U491

文献标识码：A

Shortest Path Algorithm Based on the Weighted Distance in Complex Bus Transfer Network

Zheng Jianchen¹, Chen Jianyu¹, Long Yanjun²
(1. School of Transportation and Logistics, Southwest Jiaotong University, Chengdu Sichuan 610031, China; 2. School of Art and Communication, Southwest Jiaotong University, Chengdu Sichuan 610031, China)

Abstract：In order to study the actual travel distance of passengers using public transportation, this paper develops a distance-weighted complex bus transfer network with the geodetic coordinates of bus stops based on the Space P topological mapping method in the complex network theory. On the basis of the weighed network, the paper further develops a shortest path calculation algorithm, which guarantees that the path is the shortest based on the premise of having the minimum transfer times. Then, data from Chengdu public transportation network is used to validate the proposed algorithm. Comparison with the Floyd algorithm indicates that the proposed algorithm has slightly increased the average shortest distance by 3.7 km but decreases the average transfer by 0.64 times, which is more in agreement with travel habits of passengers. Finally, the effectiveness of the algorithm is verified by experiments with randomly selected bus stops. The results show that a shortest path with minimum transfer times can be obtained with the proposed algorithm.

Keywords：complex network; bus transfer; shortest path algorithm；weighted distance