课程设计（论文）-基于交通咨询系统的最短路径算法与实现.doc

图论期末论文论文题目： 基于交通咨询系统的最短路径算法与实现 学生姓名： 学 号： 专 业： 指导教师： 完成日期： 2015年 12月 12日基于交通系统的最短路径算法与实现 摘 要目前在交通咨询领域，最短路径算法的研究和应用越来越多，其中最短路径算法的效率问题是普遍关注并且在实际应用中迫切需要解决的问题。随着现代生活节奏的加快，以及城市汽车数量的不断增加，交通网络也越来越发达，在交通工具和交通方式不断更新的今天，人们在旅游、出差或者其他出行时，不仅会关心费用问题，而且对里程和所需要的时间等问题也特别感兴趣。为了能够更方便人们的出行，我们就应该以最短路径问题建立一个交通咨询系统。这样的一个交通系统可以回答人们提出的有关交通的所有问题，比如任意一个城市到其他城市的最短路径，或者任意两个城市之间的最短路径问题。本文通过对最短路径算法的分析，研究和实现，即经典的Dijkstra算法。讨论了算法的思想、原理、实现方法、数据结构还有算法描述。针对现代交通网络现状特点，分析和研究适合道路的经典最短路径算法，探讨了在交通网络路线优化过程中需要特别处理的几个问题，并在理论上给出相应的合理的解决方案。关键词：交通咨询 最短路径 Dijkstra算法 引 言最短路径问题一直在计算机科学、交通工程学、地理信息系统、运筹学等学科中是一个研究的热点，它不仅是资源分配问题解决的基础，更是线路选择问题解决的基础，特别是在地图、车辆调度以及路由选择方面有着广泛的应用。最短路径问题最直接的应用当数在地理信息领域中，例如：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数组最终存放源点到个顶点的最短路径经过的顶点。3.计算步骤如下图所示：由F到A的路径有三条：F A：24；F B A：5+18=23；F B C A：5+7+9=21第一条最短路径为与源点V邻接顶点的弧集合中，权值最小的弧。下一条长度次短的最短路径是：假设该次短路径的终点是，则这条路径或者是，或者是，它的长度或者是从V到弧上的权值，或者是V到路径长度与到的弧上权值之和。引进一个辅助向量D，它的每个分量Di表示当前找到的从源点V到每个终点的最短路径的长度。设用带权的邻接矩阵distij来表示有向图，distij表示弧上的权值，若不存在，则置distij为某一最大值。向量S为已找到从V出发的最短路径的终点的集合，其初始值为空集。算法按下面的步骤进行： 从V出发到图上其余各个顶点（终点）可能达到的最短路径长度的初始值为：Di=distORDINAL(V)i，ViV其中ORDINAL(V)表示顶点V在有向图中的序号 选择Vj，使Dj=MinDi|Vi S，ViVVj就是当前求得的一条从V出发的最短路径的终点，且令S=Sj即将j加入到S集合中。 修改从V出发到集合V-S上所有顶点Vk可达到的最短路径长度。如果Dj+distjkDk则修改Dk为Dk=Dj+distjk 重复操作（2），（3）共n-1次。最后求得从V到图上其余各定点的最短路径是依路径长度递增的序列。二、交通咨询系统的实现1.系统设计流程该交通咨询系统要完成城市网络图的存储，并要实现求任意一个城市顶点到其他城市顶点的最短路径问题，还要实现任意两个城市顶点间的最短路径问题。故设计要分成三部分，一是建立网络交通的存储结构，二是解决单源最短路径问题；最后时限两个城市之间的最短路径问题。2. 系统构架设计首先总体的步骤是：Dijkstra算法的具体流程图如下：3.系统详细设计程序源代码如下：/Dijkstra算法package Test;import java.util.TreeMap;import java.util.ArrayList;import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.IOException;class Point private int id;/ 点的idprivate boolean flag = false;/ 标志是否被遍历int sum;/ 记录总的点个数private TreeMap thisPointMap = new TreeMap();/ 该点到各点的距离。BufferedReader bufr = new BufferedReader(new InputStreamReader(System.in);Point(int sum) / 构造函数 带有顶点个数this.sum = sum;public void setId(int id) / 设置顶点idthis.id = id;public int getId() / 获得顶点idreturn this.id;public void changeFlag() / 修改访问状态。this.flag = true;public boolean isVisit() / 查看访问状态return flag;public void setLenToOther()throws IOException/ 初始化改点到各顶点的距离。System.out.println(=请输入顶点 + (this.id + 1) + 至其他各顶点的边距=);for (int i = 0; i sum; i+) if (i = this.id)thisPointMap.put(this.id, 0);else System.out.print(至 顶点 + (i + 1) + 的距离 ：);boolean flag =true;int len = 0;while(flag)try len = Integer.valueOf(bufr.readLine();flag = false; catch (NumberFormatException e) System.out.print(输入有误，请重新输入：);thisPointMap.put(i, len);/ 该点到顶尖id的 距离。public int lenToPointId(int id) return thisPointMap.get(id);class Dijkstra public static void main(String args)throws IOException ArrayList point_arr = new ArrayList();/ 存储点集合BufferedReader bufr = new BufferedReader(new InputStreamReader(System.in);System.out.print(请输入顶点个数： );int sum = 0;boolean flag =true;while(flag)try sum = Integer.valueOf(bufr.readLine();flag = false; catch (NumberFormatException e) System.out.print(输入有误，请重新输入：);for (int i = 0; i sum-1 | start 0)throw new NumberFormatException();flag2 = false;catch (NumberFormatException e) System.out.print(输入有误，请重新输入：);showDijkstra(point_arr, start);/ 单源最短路径遍历public static void showDijkstra(ArrayList arr, int i) System.out.print(顶点 + (i + 1);arr.get(i).changeFlag();Point p1 = getTopointMin(arr, arr.get(i);if (p1 = null)return;int id = p1.getId();showDijkstra(arr, id);public static Point getTopointMin(ArrayList arr, Point p) Point temp = null;int minLen = Integer.MAX_VALUE;for (int i = 0; i arr.size(); i+) / 当已访问 或 者是自身或者无该路径时跳过。if (arr.get(i).isVisit() | arr.get(i).getId() = p.getId() | p.lenToPointId(i) 0)continue;else if (p.lenToPointId(i) );return temp;4. 测试数据及分析Dijkstra算法运行结果如下：三、设计总结城市现代化的目的，说到底是为了人的现代化。交通咨询现代化作为城市现代化的重要内容，首先应是城市居民的生活交通现代化，这是以人为本原则的基本含义和根本要求。一般来说，实现居民生活交通现代化（主要是交通咨询的现代化）便可以满足城市生产和经营交通现代化的要求。交通咨询系统服务于城市现代化发展战略，以建设现代化交通为目标，坚持以人为本原则，优化交通结构，大力发展公共交通。本次设计只是实现了两点之间最短路径可行距离的查询，而在现实生活中我们不仅要考虑两点之间的最短距离，还要考虑转车次数，这正是本次设计的不足之处。调查表明人们在出行时往往更倾向于转车次数较少的路线，这样便降低了人们的办事效率。因此，完善的交通咨询系统对两点之间的最短路径的查询应以转车次数少为条件。参 考 文 献1 图论及其应用 M.北京，清华大学出版社，2012. 2 严蔚敏。数据结构（C语言版）M.北京，清华大学出版社，1997.3 周先曙。最短路径问题及其解法研究J,电脑知识与技术，2010，（06