图论论文

图论期末论文论文题目：基于交通咨询系统的最短路径算法与实现学生姓名：学号：专业：指导教师：完成日期：2015年12月12日1基于交通系统的最短路径算法与实现摘要目前在交通咨询领域，最短路径算法的研究和应用越来越多，其中最短路径算法的效率问题是普遍关注并且在实际应用中迫切需要解决的问题。随着现代生活节奏的加快，以及城市汽车数量的不断增加，交通网络也越来越发达，在交通工具和交通方式不断更新的今天，人们在旅游、出差或者其他出行时，不仅会关心费用问题，而且对里程和所需要的时间等问题也特别感兴趣。为了能够更方便人们的出行，我们就应该以最短路径问题建立一个交通咨询系统。这样的一个交通系统可以回答人们提出的有关交通的所有问题，比如任意一个城市到其他城市的最短路径，或者任意两个城市之间的最短路径问题。本文通过对最短路径算法的分析，研究和实现，即经典的Dijkstra算法。讨论了算法的思想、原理、实现方法、数据结构还有算法描述。针对现代交通网络现状特点，分析和研究适合道路的经典最短路径算法，探讨了在交通网络路线优化过程中需要特别处理的几个问题，并在理论上给出相应的合理的解决方案。关键词：交通咨询最短路径Dijkstra算法2引言最短路径问题一直在计算机科学、交通工程学、地理信息系统、运筹学等学科中是一个研究的热点，它不仅是资源分配问题解决的基础，更是线路选择问题解决的基础，特别是在地图、车辆调度以及路由选择方面有着广泛的应用。最短路径问题最直接的应用当数在地理信息领域中，例如：GIS网络分析、城市规划、电子导航等等。在交通咨询方面，寻找交通网路中两个城市之间最短的行车路线就是最短路径问题的一个典型的例子。随着交通网络越来越发达，人们在旅游、出差或者其他出行时，不仅会关心费用问题，而且对里程和所需要的时间等问题也特别感兴趣。为了能够更方便人们的出行，我们就应该以最短路径问题建立一个交通咨询系统。这样的一个交通系统可以回答人们提出的有关交通的所有问题，比如任意一个城市到其他城市的最短路径，或者任意两个城市之间的最短路径问题。本题目的意义在于，用java软件技术实现最短路径算法在交通咨询中的重要应用，对模拟结果进行分析讨论，为将来能够有效解决各大城市的交通问题提供可靠的依据。一、Dijkstra算法Dijkstra算法是一个按权值大小递增的次序产生最优路径的算法，用于计算从有向图中任意结点到其他结点的最优路径。设一个有向图G=(V,E),已知各边的权值，以某指定点为源点，求到图的其余各点的最短路径。1.算法思想分析1959年狄克斯特拉（Dijkstra）提出一个按路径“长度”递增的次序产生最短路径的算法，即：把图中所有的顶点分成两组，第一组S包括已经确定最短路径的顶点，初始时只含有源点；第二组V-S中包括尚未包括最短路径的顶点，初始时含有图中初源点之外的所有其他顶点。按路径长度递增的顺序计算源点到各顶点的最短路径，逐个把第二组中的顶点加到第一组中去，直至V=S。2.实现思路有向网用邻接矩阵cost[][]表示，其中规定：（1）如果两个顶点之间无直接路径，即弧对应权值为无穷大；（2）两个顶点之间有直接路径的，矩阵中的权值就是弧对应的公路长度；（3）对应的值为0。S集合初始存放最短路径的源点，计算过程中将已经确定了最短路径的顶点加到S中去。Dist数组最终存放源点到各顶点的最短路径结果。Path数组最终存放源点到个顶点的最短路径经过的顶点。33.计算步骤如下图所示：由F到A的路径有三条：FA：24；FBA：5+18=23；FBCA：5+7+9=21第一条最短路径为与源点V邻接顶点的弧集合中，权值最小的弧。下一条长度次短的最短路径是：假设该次短路径的终点是，则这条路径或者是，或者是，它的长度或者是从V到弧上的权值，或者是V到路径长度与到的弧上权值之和。引进一个辅助向量D，它的每个分量D[i]表示当前找到的从源点V到每个终点的最短路径的长度。设用带权的邻接矩阵dist[i][j]来表示有向图，dist[i][j]表示弧上的权值，若不存在，则置dist[i][j]为某一最大值。向量S为已找到从V出发的最短路径的终点的集合，其初始值为空集。算法按下面的步骤进行：①从V出发到图上其余各个顶点（终点）可能达到的最短路径长度的初始值为：D[i]=dist[ORDINAL(V)][i]，Vi∈V其中ORDINAL(V)表示顶点V在有向图中的序号②选择Vj，使D[j]=Min{D[i]|ViS，Vi∈V}Vj就是当前求得的一条从V出发的最短路径的终点，且令S=S∪{j}即将j加入到S集合中。③修改从V出发到集合V-S上所有顶点Vk可达到的最短路径长度。如果D[j]+dist[j][k]D[k]则修改D[k]为D[k]=D[j]+dist[j][k]④重复操作（2），（3）共n-1次。最后求得从V到图上其余各定点的最短路径是依路径长度递增的序列。4二、交通咨询系统的实现1.系统设计流程该交通咨询系统要完成城市网络图的存储，并要实现求任意一个城市顶点到其他城市顶点的最短路径问题，还要实现任意两个城市顶点间的最短路径问题。故设计要分成三部分，一是建立网络交通的存储结构，二是解决单源最短路径问题；最后时限两个城市之间的最短路径问题。2.系统构架设计首先总体的步骤是：Dijkstra算法的具体流程图如下：53.系统详细设计程序源代码如下：//Dijkstra算法packageTest;importjava.util.TreeMap;importjava.util.ArrayList;importjava.io.BufferedReader;importjava.io.InputStreamReader;importjava.io.IOException;classPoint{privateintid;//点的id6privatebooleanflag=false;//标志是否被遍历intsum;//记录总的点个数privateTreeMapInteger,IntegerthisPointMap=newTreeMapInteger,Integer();//该点到各点的距离。BufferedReaderbufr=newBufferedReader(newInputStreamReader(System.in));Point(intsum){//构造函数带有顶点个数this.sum=sum;}publicvoidsetId(intid){//设置顶点idthis.id=id;}publicintgetId(){//获得顶点idreturnthis.id;}publicvoidchangeFlag(){//修改访问状态。this.flag=true;}publicbooleanisVisit(){//查看访问状态returnflag;}publicvoidsetLenToOther()throwsIOException{//初始化改点到各顶点的距离。System.out.println(=======请输入顶点+(this.id+1)+至其他各顶点的边距=======);for(inti=0;isum;i++){if(i==this.id)thisPointMap.put(this.id,0);else{7System.out.print(至顶点+(i+1)+的距离：);booleanflag=true;intlen=0;while(flag){try{len=Integer.valueOf(bufr.readLine());flag=false;}catch(NumberFormatExceptione){System.out.print(输入有误，请重新输入：);}};thisPointMap.put(i,len);}}}//该点到顶尖id的距离。publicintlenToPointId(intid){returnthisPointMap.get(id);}}classDijkstra{publicstaticvoidmain(String[]args)throwsIOException{ArrayListPointpoint_arr=newArrayListPoint();//存储点集合BufferedReaderbufr=newBufferedReader(newInputStreamReader(System.in));System.out.print(请输入顶点个数：);intsum=0;booleanflag=true;while(flag){try{sum=Integer.valueOf(bufr.readLine());flag=false;}catch(NumberFormatExceptione){8System.out.print(输入有误，请重新输入：);}};for(inti=0;isum;i++){//初始化Pointp=newPoint(sum);p.setId(i);p.setLenToOther();point_arr.add(p);}System.out.print(请输入起始顶点id：);booleanflag2=true;intstart=0;while(flag2){try{start=Integer.valueOf(bufr.readLine())-1;if(startsum-1||start0)thrownewNumberFormatException();flag2=false;}catch(NumberFormatExceptione){System.out.print(输入有误，请重新输入：);}};showDijkstra(point_arr,start);//单源最短路径遍历}publicstaticvoidshowDijkstra(ArrayListPointarr,inti){System.out.print(顶点+(i+1));arr.get(i).changeFlag();Pointp1=getTopointMin(arr,arr.get(i));if(p1==null)return;intid=p1.getId();showDijkstra(arr,id);9}publicstaticPointgetTopointMin(ArrayListPointarr,Pointp){Pointtemp=null;intminLen=Integer.MAX_VALUE;for(inti=0;iarr.size();i++){//当已访问或者是自身或者无该路径时跳过。if(arr.get(i).isVisit()||arr.get(i).getId()==p.getId()||p.lenToPointId(i)0)continue;else{if(p.lenToPointId(i)minLen){minLen=p.lenToPointId(i);temp=arr.get(i);}}}if(temp==null)returntemp;elseSystem.out.print(@--+minLen+--);returntemp;}}4.测试数据及分析Dijkstra算法运行结果如下：10三、设计总结城市现代化的目的，说到底是为了人的现代化。交通咨询现代化作为城市现代化的重要内容，首先应是城市居民的生活交通现代化，这是以人为本原则的基本含义和根本要求。一般来说，实现居民生活交通现代化（主要是交通咨询的现代化）便可以满足城市生产和经营交通现代化的要求。交通咨询系统服务于城市现代化发展战略，以建设现代化交通为目标，坚持以人为本原则，优化交通结构，大力发展公共交通。本次设计只是实现了两点之间最短路径可行距离的查询，而在现实生活中我们不仅要考虑两点之间的最短距离，还要考虑转车次数，这正是本次设计的不足之处。调查表明人们在出行时往往更倾向于转车次数较少的路线，这样便降低了人们的办事效率。因此