广东省中小城市公交线路评估.docx

摘要 本文以汕尾市城区的公交网络作为研究对象，通过分析汕尾市城区的公交换乘情况，采集汕尾市城区的公交线路及其站点信息等，选择使用java程序语言编程，运用二维数组来完成以公交线路站点的信息存储和以公交站点为结点的大矩阵的乘法算法；并运用邻接矩阵能用于求图节点之间是否能相互连通的特点，通过求矩阵的平方来完成一次换乘的功能，通过求矩阵的立方完成二次换乘的功能。后期通过确定起点来遍历站点数组寻找存在的一个或两个中点能达到终点的遍历方式，优化了邻接矩阵求平方，立方的方法来达到一次，二次换乘的目的。最后通过与各种常见的最短路径算法之间的时间效率比较，来说明邻接矩阵通过求超大矩阵的一次方和二次方来完成一次换乘和两次换乘方案的高效性以及稳定性。 关键词：公共交通；大矩阵乘法；邻接矩阵；换乘 Abstract This paper takes the public transportation network of Shanwei City as the research object, through analyzing the public transportation transfer situation of Shanwei City, collecting the public transportation line and station information of Shanwei City, choosing Java programming language, using two-dimensional array to complete the information storage of the public transportation line station and the multiplication algorithm of the large matrix with the public transportation station as the node, and using adjacency matrix It can be used to find whether the graph nodes can be connected with each other. It can complete the function of primary transfer by finding the square of the matrix, and complete the function of secondary transfer by finding the cube of the matrix. In the later stage, the starting point is determined to traverse the array of stations to find the traversal mode where one or two midpoint can reach the end point, and the method of finding the square and cube of the adjacency matrix is optimized to achieve the purpose of primary and secondary transfer. Finally, by comparing the time efficiency with other common shortest path algorithms, it shows that the adjacency matrix can achieve the efficiency and stability of one transfer and two transfer schemes by finding the first and second power of the super large matrix. Keywords: Public transport;arge matrix multiplication;djacency matrix; transfer 目 录 TOC \o "1-3" \h \z \u 第一章 绪论 1 1.1课题目的与意义 1 1.2公交站点现状 2 1.3转乘算法现状 2 1.4课题现状 3 第二章 公交换乘系统 4 2.1概述 4 2.2公交线路 4 2.2.1公交路线特点 4 2.3路径问题 5 2.4转乘算法实现 6 2.4.1最少转乘原则 6 2.4.2 Dijkstr