马玉峰(西北民族大学数学与计算机科学学院,兰州730030)
图1总体结构图
如图1所示,总体来说,系统总共分成6大部分,分别是首页、本站导航、高级搜索、公交新闻、留言板和系统维护。加入了统计客流量的计数器。搜索方式有四种,分别是车次查询、站点查询、精确查询和高级搜索。(二)数据库设计数据库用的是微软公司的Access数据库。它提供了表、查询、窗体、报表、页、宏、模块7种用来建立数据库系统的对象;提供了多种向导、生成器、模板,把数据存储、数据查询、界面设计、报表生成等操作规范化。建立的数据库名为nbos.mdb,有四个功能模块需要用到数据库,首先是公交车信息,接着是管理员信息、留言板信息、新闻,分别对应bus、ManagerMessages和News这四个表。bus表的意义在于当用户进入到查询系统界面或者管理员进入到车次管理界面的时候,系统将和bus表进行数据的交互。Manager表的意义在于,管理员进行管理员登陆的时候,需要验证管理员的信息,此时,在验证窗口中,管理员需要输入相关的信息。这四个表之间是独立的,相互之间没有很大影响,用户一登陆上网站,可以到任意一个模块中。由于用到的是Access数据库,因此连接数据库用的代码是标准的微软链接代码。首先,建立数据库表格,这一步在之前已经做好了。接下来,在“控制面板”→“管理工具”→“数据源(ODBC)”中,将数据库nbos.mdb添加到数据源中,这一步是添加到系统DSN中的。接着在程序中添加如下代码:Try{Class.forName("sun.jdbc.odbc.JdbcOdbcDriver");//Microsoft连接Access标准代码}catch(ClassNotFoundExceptione){}//抛出异常try{con=DriverManager.getConnection("jdbc:odbc:nbos","","");//连接Access的Url}测试连接,如若连接成功,数据库正式建立。在接下来的调用字段名中,用到的代码为:select*frombus;//bus是表名(三)算法分析本设计用的最短路径算法是迪杰斯特拉(Dijkstra)算法,该算法按照路径长度递增的次序来产生最短路径。迪杰斯特拉算法用于求解一个有向图(也可以是无向图,无向图是有向图的一种特例)的一个点(称之为原点)到其余各点(称之为周边点)的最短路径问题。该算法的原理是,引进一个辅助向量D,它的每个分量D表示当前所找到的从始点v到每个终点vi的最短路径的长度。如D[3]=2表示从始点v到终点3的路径相对最小长度为2。这里强调相对就是说在算法过程中D的值是在不断逼近最终结果但在过程中不一定就等于最短路径长度。它的初始状态为:若从v到vi有弧,则D为弧上的权值;否则置D为∞。显然,长度为:D[j]=Min{D|vi∈V}的路径就是从v出发的长度最短的一条最短路径。下一条最短路径(设其终点为X)或者是弧(v,x),或者是中间只经过S中的顶点而最后到达顶点X的路径。算法的具体描述为:首先,用arcs表示弧上的权值。若不存在,则置arcs为∞(在本程序中为MAXCOST)。S为已找到从v出发的最短路径的终点的集合,初始状态为空集。那么,从v出发到图上其余各顶点vi可能达到的最短路径长度的初值为D=arcs[LocateVex(G,v),i]vi∈V。接着,选择vj,使得D[j]=Min{D|vi∈V-S}最后,修改从v出发到集合V-S上任一顶点vk可达的最短路径长度。迪杰斯特拉算法中的一个主要循环如下://每次求得V0到某个V顶点的最短路径,并加V到S集For(i=1;i<G.vexnum;++i){//除起点之外的所有顶点G.vexnum-1Min=INFINITY;//当前所知离V0定点最近的距离For(w=0;w<G.vexnum;++w){If(!final[w])//W顶点在V-S中If(D[w]<min){v=w;min=D[w];}//W顶点离V0顶点更近Final[v]=TRUE;//离V0顶点最近的V加入S集}For(w=0;w<G.vexnum;++w){//更新当前最短路径及距离If(!final[w])&&(min+G.arcs[v][w]<D[w])){//修改D[w]和P[w]D[w]=min+G.arcs[v][w];P[w]=p[v];p[w][w]=TRUE;//p[w]=P[v]+[w]}}}根据带权矩阵,再按照迪杰斯特拉算法,由于除去起点,剩下5-1=4个顶点,故i<G.vexnum=5,故i最大取4。则可得从V0到其余各顶点最短路径,以及运算过程中D向量的变化情况。参考文献:[1]刘敏恒,孙涛,陈继努.基于VB.NET的智能公交管理系统软件平台的开发[J].重庆邮电学院学报(自然科学版),2006(增刊):153-155[2]王庆平,张兴芳,宋颖等.城市公交换乘的数学模型及其算法实现[J].计算机工程与应用,2008,44(7):246-248[3]李旭华.公交线路网络分析关键技术研究[D].太原:中北大学,2005,35(12);145-150