最优路径查询是公交信息系统中的关键技术。本论文从网络分析的理论基础及道路网络的拓扑性质出发，提出了一种适于最短路径算法的空间数据组织方式。结合道路网络的特点，在构造邻接结点矩阵来表达网络结构的基础上，根据人们日常的乘车习惯，提出了基于改进的广度优先搜索（BFS）算法实现换乘次数最少和基于迪杰斯特拉（Dijkstra）最短路径算法实现路径最短的两种最优路径查询方案。
本论文使用Visual Studio C#.NET 2003和SQL Server 2000，基于昆明市地图开发了一个实际的公交信息系统，实现了道路网络中任意两点间最少换乘路径和最短路径的快速查询。
【关键词】 公交信息系统 最少换乘 最短路径 Dijkstra算法 BFS算法
Abstract
The optimum path query is the key technology in the Bus Information System.
Based on the theories of network analysis and the topology of route network, a new method of spatial data structure for the algorithm which is suitable for the Dijkstra’s algorithm method is proposed in this paper. Combined with the characteristics of route network , and based on our habits , put the method of fewest transfers which is base on the Breadth-First Search algorithm and the method of shortest path which is base on the Dijkstra’s algorithm .
The paper use Visual Studio C#.NET 2003 and SQL Server 2000 ,based on the map of
【Key Word】 Bus Information System , Fewest Transfers , Shortest Path , Dijkstra’s Algorithm , Breadth-First Search
3.2.1 迪杰斯特拉（Dijkstra）算法基本思想... 30
3.2.2 迪杰斯特拉（Dijkstra）算法的具体实现... 31
3.3.2 广度优先搜索（BFS）算法的基本思想... 35
3.3.3 广度优先搜索（BFS）算法实现最少换乘路径的搜索... 37
随着社会的发展，城市的日益扩大，城市交通问题变得日益突出。城市公交网络在城市的发展中起到举足轻重的作用，伴随城市公交网络发展而产生的城市公交信息系统，日渐成为城市居民的生活指南，这要求它必然要提供公交网络最优路径查询的功能。根据人们日常的乘车习惯，换乘次数最少往往是人们选择出行路径的首要考虑因素，越少的换乘次数可以节省人们出行的开销。其次路径最短也是人们考虑的一个重要因素。
本论文首先介绍了网络分析的理论基础知识，通过分析道路网络的拓扑性质，最终采用了用构造邻接结点矩阵来表达网络结构的空间数据组织方式，这种组织方式适合于最优路径查询算法。
接着在SQL Server 2000 中实现了昆明市部分地图数据的存储，其中包括了部分建筑物数据信息的存储和部分公交站点数据信息的存储。
然后重点分析了迪杰斯特拉（Dijkstra）最短路径算法和广度优先搜索（BFS）算法，并分别对两种算法进行了优化，使其更加适于公交网络中的最优路径的搜索。
最后以昆明市地图为基础，实现了一个具体的公交信息系统。系统开发前台使用了Visual Studio C#.NET 2003，后台数据库使用SQL Server 2000。系统一方面实现了基本信息的查询，包括建筑物的位置，坐标等。另一方面实现了公交线路的查询，查询方式按照“路径最短”和“换乘最少”两种方式分类，可以根据乘客的实际需求选择自己所需的方式。通过这个功能，用户可以查询到公交网络中任意两点间的换乘最少和路径最短的乘车路线，为乘客出行带来了很大的方便。1193
[1] [2] [3] [4] [5] [6] [7] [8] [9] [10] ... 下一页 >>