关键词: 公交网络, 二部图, 路径搜索

Abstract: The paper describes the bipartite graph model to represent public transport networks.In bipartite graph，bus stops and routes are all considered as vector，and the length of path is calculated by links’ referencing distance.Based on the bipartite graph model and Dijkstra’s algorithm，an optimal path-finding algorithm for public transport network is designed.It is found that the proposed algorithm can efficiently consider both the transfer factor and the distance factor of the path choice of public transport passengers.Furthermore，a multi-path selection algorithm for public transport network is designed based on the iterative penalty method.Finally，a numerical example is provided to demonstrate the effectiveness of the algorithm.

Key words: public transport networks, bipartite graph, path-finding