基于矩阵运算的公交查询高效算法

计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (10): 198-200.

基于矩阵运算的公交查询高效算法

鲍江宏,关毅璋

华南理工大学数学科学学院，广州 510641

收稿日期:2007-07-16 修回日期:2007-10-22 出版日期:2008-04-01 发布日期:2008-04-01
通讯作者: 鲍江宏

Efficient algorithm based on matrix computation for querying transit network

BAO Jiang-hong,GUAN Yi-zhang

School of Mathematical Sciences，South China University of Technology，Guangzhou 510641，China

Received:2007-07-16 Revised:2007-10-22 Online:2008-04-01 Published:2008-04-01
Contact: BAO Jiang-hong

摘要/Abstract

摘要： 目前绝大多数公交查询算法是基于最短路径查找算法的改进，但最短路径算法本质上不适合公交线路的查询。定义一种新型的直达矩阵，并提出两种新的矩阵运算。在此基础上，建立起了一种基于矩阵运算的高效公交查询算法。对算法进行分析后，引入了一些重要的改进。最后在计算机中把提出的算法应用到实际数据，取得了理想的效果。

关键词: 公交网络, 矩阵运算, 最短路径查找算法

Abstract: Most of the developed algorithms are based on the improvement to the shortest path finding algorithm，however，the algorithm is essentially unsuitable for querying transit network.A new arrival matrix is defined and two matrix computation are originally proposed in this work.Then an efficient algorithm based on matrix computation for querying transit network is developed.Having analyzed it in detail，some important improvements are impacted to the new algorithm.Finally，the algorithm is applied to the practical data by programming，and a good result has been obtained.

Key words: transit network, matrix computation, shortest path finding algorithm

鲍江宏,关毅璋. 基于矩阵运算的公交查询高效算法[J]. 计算机工程与应用, 2008, 44(10): 198-200.

BAO Jiang-hong,GUAN Yi-zhang. Efficient algorithm based on matrix computation for querying transit network[J]. Computer Engineering and Applications, 2008, 44(10): 198-200.

[1]	汪琳娜1，2，杨新3，杨习贝4. 复合决策粗糙建模与计算方法研究[J]. 计算机工程与应用, 2018, 54(19): 122-128.
[2]	王佳1，2，符卓1. 双层城市公交网络设计及优化方法研究[J]. 计算机工程与应用, 2012, 48(36): 1-8.
[3]	杨靖1，林益2，洪露3，李泽滔1. 一种改进的D-S证据理论合成方法[J]. 计算机工程与应用, 2012, 48(20): 150-153.
[4]	游源¹，齐欢¹，胡祥恩². 树状模型中EM算法的矩阵形式[J]. 计算机工程与应用, 2011, 47(5): 32-34.
[5]	闫小勇¹，尚艳亮². 基于二部图模型的公交网络路径搜索算法[J]. 计算机工程与应用, 2010, 46(5): 246-248.
[6]	周志顺，徐成，刘彦. 三维荧光光谱分析的关键部件硬件设计研究[J]. 计算机工程与应用, 2010, 46(12): 60-63.