Gis最短路径等网络分析问题网络分析的的毕业论文.doc

1、目录摘要1第一章 绪论1第二章 网络的最短路问题的基础知识2第三章 网络的最短路问题的算法研究9第四章 最短路问题的应用28参考文献:51摘要第一章 绪论二十世纪中后期，随着计算机的出现和发展，图论的研究得到广泛重视，最短路径问题是图论中的一个典范问题，它已经被应用于众多领域.最短路径问题最直接的应用当数在地理信息领域，如：GIS网络分析、城市规划、电子导航等.在交通咨询方面，寻找交通路网中两个城市间最短的行车路线就是最短路径问题的一个典型的例子.在网络通信领域，信息包传递的路径选择问题也与最短路径问题息息相关.举个例子，OPSF开放路由选择协议，每个OPSF路由器都维护一个描述自治系统拓扑结

2、构的数据库，通过这个数据库构建最短路径树来计算路由表，从而跟踪自治系统范围内到每个目标的最短路径.在图象分割问题中，最短路径也有直接的应用：在语音识别中，一个主要的问题就是区别同音词，例如，to、two、too.为解决这个问题，我们需要建一个图，顶点代表可能的单词，边连接相邻的单词，边上的权代表相邻的可能行大小.这样图中的最短路径，就是对句子的最好解释.由于最短路径问题的广泛应用，很多学者都对此进行了深入的研究，也产生了一些经典的算法.近些年来，对最短路径研究的热度依然不减，并且时间复杂度降得越来越低.所以在本课题中我们将提出不仅是以前我们学习过的一些经典的算法，我们还将提出一些以前没有学习过

3、的更有应用空间的算法.以及各算法之间的比较.最后还将把这些算法在现实中的应用最一些简单的介绍.第二章 网络的最短路问题的基础知识2.1 图的基本概念（1）图定义：一个（无向）图G 是一个有序二元组（V，E），其中是顶点集，是边集，且是一个无序二元组，它表示该边连接顶点与.图1就是一个图. 说明：在保持图的点边关系不变的情况下，图形的位置、大小、形状都是无关紧要的.若，则称连接与；点和称为的顶点，称或与关联，与是邻接的顶点；如果两条边有一个公共顶点，则称这两条边是邻接的；（2）环定义：两个顶点重合为一点的边称为环(如图图1中).V1V2V3V4V5图1（3）重边定义：如果有两条边的顶点是同一对顶

4、点，则称这两条边为重边（如图1中与中有两条边相连）.（4）孤立点定义：不与任何边关联的点称为孤立点（如图1中）；（5）无环图定义：没有环的图称为无环图；（6）简单图：定义：既没有环也没有重边的图称为简单图.设G=（V，E）是一个简单图，则显然有.（7）完全图定义：若上式中等号成立，则说明该图中每对顶点间恰有一条边相连，称此图为完全图.（8）补图定义：一个简单图的补图是与有相同顶点的简单图，且中两个点相邻当且仅当它们在中不相邻.（9）二分图定义：一个图G=（V，E），若存在V 的一个分划（，），使得每条边有一个顶点在中，另一个在中，则称为二分图.（10）子图、支撑子图定义：设有两个图，如果，则称

5、为的支撑子图.（11）点导出子图定义：设有图G=（V，E），是的非空子集，若以为点集，以两点均在中的所有边为边集的子图称为由导出的的子图，记为，简称点导出子图.（12）边导出子图定义：若是的一个非空子集，则以为边集以中边的所有顶点作为点集的子图，称为由导出的的子图，记为，简称边导出子图.（13）度：定义：图中顶点的度为与关联的边的数目（与关联的每个环算作两条边），记为.结论：设G=（V，E）是一个图，则，即度数为奇数的顶点有偶数个.2.2有向图（1）有向图定义：一个有向图是一个有序二元组，其中是顶点集，称为的弧集，为一个有序二元组.称为连向的弧，为的出弧，的入弧；称为得尾，称为的头；称为的前继

6、，称为的后继.图2就是一个有向图.V1V2V3图2（2）环定义：头和尾重合的弧称为环.（3）重弧定义：若两条弧有相同的头和尾，则称这两条弧为重弧.（4）简单有向图定义：没有环和重弧的有向图称为简单有向图（5）基图定义：把有向图中每条弧用边来代替，得到一个无向图，称为得基图.（6）完全有向图定义：设G=（V，E）是一个简单有向图，则，若等号成立，则称这样的图为完全有向图.（7）出度、入度定义：有向图中顶点的出弧的数目称为的出度，记为；顶点入弧的数目称为的入度，记为.结论：设G=（V，E）是一有向图，则 类似地可以定义有向图的子图，支撑子图，点，边导出之子图的概念.（8）网络定义：设是一个图，若对

7、的每一条边都赋以一个实数，称为边的权，则连同边上的权称为一个网络，记为.同样可以定义有向网络.在此主要讨论网络上的各种优化问题.无向网络可以转化为有向网络，具体做法为：把无向网络中每条边代之以一对弧（）和（），且两条弧的权都等于边的权.2.3连通性（1） 途径、迹、路定义：设有图 G=（V，E），如果它的某些顶点与边可以排成一个非空的有限交错序列，这里该途径中边互不相同，则称为迹；如果顶点互不相同，则称它为路.显然路必为迹，但反之未必.（2） 闭路径定义：如果某途径至少含一条边，且起点与终点重合，则称它为一条闭途径.类似可定义闭迹和回路（又称圈）.注意：若为简单图，则两个顶点间边若存在必是唯一

8、的，故由到的一条途径可以用顶点序列表示.（3） 连通图：定义：图中若存在一条从顶点到的途径，则称与是连通的.如果图中任何两个顶点都是连通的，则称是连通图.例如，完全图是连通的.二分图，则只要，中有一个大于1，则一定不是连通图.（4） 连通子图定义：如果是的子图，且是连通的，则称为的连通子图.（5） 极大连通子图定义：如果为的连通子图，且不存在连通子图，使是的子图.图的极大连通子图又称为的连通分支.（6） 有向途径定义：设有一个有向图，中某些顶点与弧组成的非空有限序列这里，且，则称它为从到的有向途径.类似可定义有向迹，有向路，有向闭途径，有向闭迹，有向回路（有向圈）.当是简单有向图时，从到的一条

9、有向途径可简记为（）.（7） 强连通定义：中若既存在一条从顶点到的有向途径，又存在从到的有向途径，则称和是强连通的.如果中任意两顶点都是强连通的，则称是强连通的.（8） 强连通分支定义：的极大强连通子图称为强连通分支.注：若强连通，则恰有一个强连通分支.结论：若为有个连通分支的简单无向图，则的邻接矩阵为准对角矩阵若为有个强连通分支的简单有向图，则的邻接矩阵为准上三角矩阵2.4割集（1） 割边定义：设有图，是的一条边，如果从中删去，使它的连通分支数量增加1，则称是的割边.显然，的一条边是割边当且仅当该边不包含在的任何闭迹中.（2） 边割定义：设是的一个非空子集，记，如果，且从中删去这些边后，的连

10、通分支至少增加1，则称是的一个边割.（3） 割集定义：若是一个边割，且的任何真子集都不是边割，则称它为极小边割，的极小边割又称为割集.结论：任给图，设是图的圈，是图的割集，用表示的边集.如果，那么.（4） 弧割定义：设是一个有向图，记，如果，则从中删去这些弧以后，的强连通分支数至少增加1，称它为的一个弧割.的极小弧割称为有向割集.2.5最短路问题定义：所谓最短路径是指如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条有向路径使得沿此路径上各弧的权值总和达到最小.第三章 网络的最短路问题的算法研究3.1最短路问题的提出某旅客要从杭州乘飞机前往奥地利的萨尔斯堡，

11、因为他害怕乘飞机，所以要选择一条航线，使得在空中飞行的时间尽可能的少.问题是如何选择航线以达到要求.为此构造一个无向网络总可以化成有向网络，故下面只讨论有向网络的最短路问题.设是一有向网络，为中一条有向路，称为路的权或路长.现寻找网络中自某一指定顶点到另一指定顶点的最短有向路.3.2 Bellman最短路方程设有一个有向网络，.若用表示自顶点到顶点的最短有向路长，用表示弧（）的长度，若，则定义，则对一切有且当且仅当弧在自顶点到顶点的最短有向路上.因为所有均表示自到的最短路长，因此这些最短路必有最后一条弧（），且该有向路上自到的一段也是最短路，故有Bellman最短路方程：即自点到各点最短路长度

12、必满足Bellman最短路方程.反过来，Bellman最短路方程的解是自点到其余各点最短路的长度.3.3无负回路网络的最短有向路的Ford算法3.3.1 Ford算法的基本思想Ford算法的思想是逐次逼近，每次逼近求出网络从到其余各顶点的带某种约束的最短路，这里的约束是路中弧数.第一次逼近是从到其他任意顶点由一条弧组成的所有路中找一条最短路，记其长度为;第二次逼近是从到由不多于两条弧组成的所有路中找一条最短路，记其长度为.一般地，第次逼近是从到由不多于条弧组成的路中找一条最短的，记其长度为.因为中自到的最短路至多含个顶点， 条弧，所以最多次逼近即可. 即为中自到的最短路长.3.3.2 Ford

13、算法的步骤为方便起见，定义.第一步 置，.第二步 令.第三步 若，停止;否则令，返回第二步.3.3.3实例 求如下图所示网络中从顶点到其余各点的最短路.V3V2V6V1V5V4解 求解过程如下:因此从到的最短路径分别为，路长分别为1，2，-3，0，2.3.4求正权网络中有向最短路的Dijkstra算法3.4.1 Dijkstra算法的基本思想对网络中每个顶点赋以一个标号，用来记录从顶点到该顶点的最短路的长度（此时称为永久标号）或最短路长度的上界（此时称为暂时标号）.算法开始时，只有顶点被赋予永久标号，其它顶点被赋予暂时标号.一般地，算法在被暂时标号的顶点中寻找一个顶点，其暂时标号最小，然后将赋

14、予永久标号，且对其余暂时标号的顶点按方式修正其标号.算法在所有顶点均被赋予永久标号终止.3.4.2 Dijkstra算法的理论依据（1） 对于中任一顶点，其永久标号是从顶点到该顶点的最短路的长度.（2） 对于中任一顶点，其暂时标号是从顶点出发，只经过中顶点到达该顶点的最短路的长度.3.4.3 Dijkstra算法的算法步骤最短路径问题是指在一个赋权图的两个指定节点 和 之间找出一条具有最小权的路.Dijkstra 算法是一个解最短路径问题的算法，这个算法不仅可以找到最短的，路径而且可以给出从到图中所有节点的最短路径.其基本步骤如下:(1) 设，对所有的节点来说，设，并将标号为0， ，为和w之间

15、的权值(距离).(2)按照每个未标号的节点w计算， ，表示点t 到点w 之间的权值(距离) .若被修改了说明在当前得到的 到w 的最优路径上t 和w 相邻用记录下来在所有 中选择一个最小的 即，未标号.将s 标号为， 表示节点到s的最优路径的长度为且 与s 相邻.(3) 若终点v 已标号，则停止.得到一条从到v 的最优路径，否则，转向(2)再计算.3.4.4 Dijkstra算法的应用举例G以具体实例说明Dijkstra 算法的具体应用.例1. 利用Dijkstra 算法求图1 中节点A 到其它各节点的最优路径.K 20 2.9 3.2D 18N 4.4 3.5 3.2 4.5B 16HE Y

16、 4.1 2.2 PL 14 4.2 2 3.4 4.5AI 12 5.6 2.9 3 4.22.2 OMC 10 3.4JF 3.5 4 2.2 3 8 0 2 4 6 X 8 图1 10 12 14相应的权值为： 根据Dijkstra 算法的实现步骤其计算过程可归纳为表1 所示.从表1 中可以看出从 到 的最短路径为 且到的距离为=18.3 在求到最短路径的过程中到其余各点的最短路径也相应求出.若以计算一次为计算单位，则利用Dijkstra算法计算 到 最短路径时所需的计算次数= 15+14+13+ +2 = 119次表1采用Dijkstra 算法求解A到其他各节点最优路径的过程序号ABC

17、DEFGHIJKLMNOP1-4.23.42-4.23.4/A9.06.93-4.2/A-8.68.36.94-8.68.36.9/C11.910.95-8.58.3/B-10.311.210.96-8.6/B-11.510.311.210.97-11.510.3/D11.210.913.513.78-11.5-11.210.9/F13.513.713.19-11.5-11.2/E-13.513.713.110-11.5/D-13.513.713.111-13.513.713.1/J16.112-13.5/H13.7-18.016.113-13.7/H-15.916.114-15.9/L16.

18、118.715-16.1/M18.33.4.5 Dijkstra算法的不足在现行电子地图中，网络模型的规模常常较大，节点数多达上千或上万，并且对网络模型的查询也要求实时性，因此Dijkstra 算法虽然在理论上是可行的，但在实际应用中不尽人意，当网络模型中节点数和边数较多的情况下，算法的计算量较大时间花费较多效率非常低.3.4.6 改进Dijkstra 算法的基本思想及实现表1 中的数值大多数是，都是无用运算，如果节点数量很大，将极其浪费运算时间.由于，节点是否在上次已经被计算出最短路径未知，当前节点是否与节点是否相连也未知，也就是 未知，这时是已知的，故本次计算的 到底是不是，取决于上一步数

19、值和的数值，从表达式可以看出，只要这两个数值不都是，本次计算的 就不会是，所以在上面Dijkstra 算法的实现步骤第(2) 步时，先判断一下，只要原来的， 的数值中至少有一个不是，才进行下面的计算，这样就保证了当预见 是时，不对它进行计算，避免了大量无效的计算，提高了搜索效率.下面仍以一个具体实例来说明改进的Dijkstra算法的具体应用.例2 利用改进的Dijkstra 算法求图1中节点A到其他各节点的最优路径，此例的计算过程和Dijkstra 算法基本一致，只是表1 中所有标记的部分在改进Dijkstra 算法中被省去了，利用改进的Dijkstra 算法计算 到 最短路径时所需计算次数为

20、次，由此可见，改进的Dijkstra 算法确实减小了计算量(在程序设计中，判断语句所花费的时间可以忽略，并不增大计算量).347 实验对比为了更好地说明改进的Dijkstra 算法的有效性，利用C语言自行编制了最短路径搜索程序并进行了仿真实验，采用自绘制的地图，共5 张，第一张图16个节点，共24条弧;第二张图32个节点，共55条弧;第三张图43个节点，共75条弧;第四张图62个节点，共111条弧;第五张图78个节点，共139条弧，计算结果如表2 所示.从表2 可以看出，两种算法的计算量有很大的区别，改进的Dijkstra 算法较之经典Dijkstra 算法在计算量方面有很大幅度的减少，而且这

21、种减少的程度在节点数目增加(地图更大，更复杂)时，会变得越来越明显.对于实际系统，由于地图都会很大，使用改进Dijkstra 算法的改进效果将非常显著.表2 改进Dijkstra 算法和经典Dijkstra 算法计算次数比较节点数经典Dijkstra 算法改进的Dijkstra 算法1611947(39.5%)32465134(28.8%)43861234(27.2%)621830441(24.1%)782926540(18.5%)注:表中的百分数表示改进算法计算量与经典算法计算量的百分比35 算法的问题和改进3.5.1算法的基本思想算法在人工智能中是一种典型的启发式搜索算法.通过选择合适的估

22、价函数，指导搜索朝着最有希望的方向前进，以求得最优解. 算法中关键是求估价函数:其中， 是从起点到当前节点已付出的代价， 是从当前节点到目标节点 的代价估计函数，必须保证 (其中是从当前点到目标点的实际最小代价).3.5.2算法的步骤算法的搜索步骤如下:(1)给起始节点标记，对它的没有标记过的子节点进行扩展;(2)对每一个子节点计算评价函数值，按评价值的大小进行排列，找出评价值最小的节点，并给它作标记，如果当前节点就是目标节点，则停止搜索;(3) 否则，对最新被标记的节点进行第(2) 步处理并记录最短路径.3.5.3算法分析算法是利用对问题的了解和对问题求解过程和解的了解，寻求某种有利于问题求

23、解的启发信息，从而利用这些启发信息去搜索最优路径.它不用遍历整个地图，而是每一步搜索都根据启发函数朝着某个方向搜索.当地图很大很复杂时，它的计算复杂度大大优于Dijkstra 算法，是一种搜索速度非常快、效率非常高的算法.但是，相应的算法也有它的缺点.启发性信息是人为加入的，有很大的主观性，直接取决于操作者的经验，对于不同的情形要用不同的启发信息和启发函数，且他们的选取难度比较大，很大程度上找不到最优路径.下面通过一个具体加以实例说明.例3 利用算法求图1 中从 点出发到点的最优路径.解:在本例中将评价函数中的取为当前节点到起始节点的最短距离，而取为当前节点到目标节点的欧氏距离，在应用算法时除

24、采用上面Dijkstra 算法所用过的拓扑结构外，还应该再给定所有节点的坐标 如各点坐标为(0，13)， (3，16)， (3，11)，.根据算法的具体实现步骤可求得从到的最短路径其距离是 = 16.6.查看表1可知，用Dijkstra 算法搜索的最优路径是， 路径长度15.9 ，很明显算法没有找到最优路径，而且通过比较两条路径可以发现:当采用算法搜索路径时，从第二个节点就把最优路径舍弃了.3.5.4 算法改进思想及实现为了克服最优路径可能被轻易舍弃的缺点，本文提出采用多次搜索的方法，用增大计算量为代价来换取尽量多的最优路径备选结果.具体的方法如下:将经典算法搜索出原始最优路径中的节点依次进行

25、封堵后，再按照经典算法搜索在每一次封堵情况下的最优路径.最后将这些新的最优路径与原始最优路径进行对比以便确定最后的最优路径.现举例说明改进算法的具体应用.例4.利用改进的算法求图1中从点出发到点的最优路径.(1) 按算法寻找路径得到: ，路径长度16.6;(2) 封闭此路径中节点后得到的最优路径为:， 路径长度15.9;(3) 封闭此路径中节点后得到的最优路径为: ， 路径长度17.1;(4) 封闭此路径中节点 后得到的最优路径为: ，路径长度17.2;(5) 封闭此路径中节点 后得到的最优路径为: ，路径长度18.7;对前面求得的5 种路径长度进行对比，得到最优路径，其长度为15.9 ，从而

26、将此路径定为改进算法求得的最优路径.查看表1可知此路径正是采用Dijkstra算法时求得的最优路径.3.5.5 实验对比为了进一步验证改进算法的有效性利，用C 语言自行编制了最短路径搜索程序并进行了仿真实验.以78个节点(含1个起始节点，77个待规划节点) 的地图作为对象得到的仿真结果.采用经典算法对77个节点分别进行路径规划，有45个找到了最优路径而采用改进的算法对77个节点进行路径规划时，有68个找到了最优路径，有8个节点虽未找到最优路径但得到了比经典算法更短的路径，只有1个节点和经典算法结果一致.这充分说明改进的算法较之经典的算法在搜索最优路径的成功率方面具有明显的优势.3.6 结论本文

27、对经典Dijkstra 算法和算法进行了改进，改进后的算法具有以下特点.(1)改进的Dijkstra 算法能在很大程度上节省计算量，提高路径规划的速度.(2)改进的算法虽在一定程度上增大了计算量(但远远小于Dijkstra 算法的计算量)， 却大大增大了搜索到最优路径的成功率.3.7 混合步长网络漫游最短路算法 3.7.1 引言网络最短路问题一直是网络理论与实践的重要研究课题之一，是在工农业生产及各项经济活动中非常具有实用价值的一门计算技术，是系统工程和运筹学研究的一个重要分枝随着图与网络理论的不断发展与完善和计算技术、计算手段的不断进步，为新的网络最短路算法的研究提供了前提和条件经过深入的研

28、究探索和实践，本文提出一种任意路权网络最短路的新算法混合步长网络漫游法3.7.2 网络漫游法原理在一个给定的任意路权网络图中，为该网络的点集合，为该网络的弧集合，为网络各弧的权数集合确定一个点 作为漫游网络的起点，并记该点的漫游路长为零 ，其余各点的漫游路长 ，以此作为初始状态之后，每一步都以当前漫游点的路长来修正其余相关连点的路长，并选择一个新的漫游点，如此往复，直至不再有可以漫游的点为止若从起始点 到任意点的直接路长为 （为网络的顶点数，若两点和之间没有直接的弧连接，则），则以修改各点的初始漫游路长， 作为第一步各点的漫游路长，并选择所对应的点作为第一步的漫游点，称之为当前漫游点一般而言，

29、经过步漫游到达第点，则第点为当前漫游点，该点的当前漫游路长为 为寻找下一步的漫游点，要计算 ，并以作为点第 步的漫游路长，选择 点作为第 步的漫游点，如此循环，直至各能够到达的点均已漫游过且各点已不存在更短的漫游路长时，漫游终止同时得到了从起始点到各点的最短路3.7.3网络漫游法的特点3.7.3.1 混合步长每次从当前漫游点寻找下一漫游点时，采用了算式，所以，下一漫游点的路长不只是第步中的最短路，而且是在第步、第 步、 、第1步、第0步中的最短路，是当前步长内所有步数能够到达该点的最短路 3.7.3.2路长递减性由于采用了算式作为第点的第步的路长，它小于等于 步之内任一步长的路长，具有递减性3

30、.7.3.3条件记忆性由第k步的当前漫游点寻找下一漫游点时，是在除当前点之外的其它点中寻找其余的点分为两类，一类是还没有漫游过的点，它自然属于寻找的范围；另一类是已经漫游过的点，这类点分为两种情况，其一是该点记录的 步步长之内的最短路值是该点作为漫游点时的路长，则该点不在寻找之列，即该点已漫游过这件事是在记忆之中的，其二是该点虽然已漫游过，但在其后的漫游中更新了该点漫游时的路长值，则该点在寻找范围之列，即对该点已漫游过这一事实失去记忆，如同没有漫游过的点一样也就是说，若该点作为漫游点时的路长值一直保持为该点的最短漫游路长，则对该点保持记忆；若该点作为漫游点时的路长值已发生变化，则对该点的漫游失

31、去记忆3.7.4 网络漫游法的算法对于给定的任意路权网络，按照如下步骤进行网络漫游，只要网络中不含负回路，最终总可以求得从起始点到其所能到达的所有点的最短路当然，也可以从终点 反向漫游，以求得从网络的任意一点到终点 的最短路3.7.4.1 确定漫游起始状态若求从某点到其它各点的最短路，则以 作为漫游的起始点（当前漫游点），并记该点的起始漫游路长为零，其余各点的漫游路长为无穷大（注：若求其它各点到终点 的最短路，则以 作为漫游起点，进行反向漫游即可）3.7.4.2 从当前漫游点向外探索计算从当前漫游点走到其它各点所产生的路长 3.7.4.3确定各点新的漫游路长将各点的 与其当前的最短路长进行比较

32、，选取较小者作为该点新的漫游路长，即 3.7.4.4 作漫游标记当从本漫游点向外探索之后则对其作一标记，表示此点已漫游过在以后的漫游中保持此标记，直到该点有更短的漫游路长出现时，则除去该点的漫游标志3.7.4.5 确定新的漫游点在当前没有作漫游标记的点中，选取所对应的点作为新的漫游点返回3.2继续漫游3.7.4.6 漫游终止条件当给当前漫游点标上漫游标记，而其它点要么是标有漫游标记的点，要么是路长为无穷大的点，故找不到新的漫游点，则算法终止3.7.5算例网络漫游法求最短路可以采用手工表上作业法，也可以采用计算机程序算法手工表上作业法对于一般的网络而言是简便易行、步骤清晰对于较复杂的网络则采用计

33、算机程序算法为宜现以例演示手工表上作业法（见图1和表1） 表1 任意路权网络漫游法表上作业法示例 3.7.5.1 算法说明 步长为零的行为起始状态行，点为漫游起点并标记当前漫游点标记（ ），它的起始路长为零，其余各点的起始路长为无穷大 步长1-6都分成了两行，上面一行称为计算行，它是从当前漫游点走到下一漫游点的总路长 ；下面一行称为选取行，它要做三件事：a 选取者作为第点的当前漫游路长b 将上一步的漫游点标记（ ）在本步中改变为已漫游标记 如果某一点在上一步中就是带有已漫游标记的，且新的漫游路长，则保留其漫游标记，否则，去掉漫游标记c 从当前选取行中没有漫游标记 的数值中，选定一最小值，并做上

34、当前漫游点标记（ ） 如果当前选取行中已不存在不带漫游标记的有限数值，则漫游终止，当前选取行中的数值就是从起始点到各点的最短路长3.7.5.2 寻找最短路线从表中最后一行的最短路长向上寻找，只观察各步的选取行，当遇到某选取行的值大于当前值时，则横向寻找该步的漫游点，并从该漫游点以同样的方法向上寻找，直到起始点为止这其间所经过的漫游点的集合就是所对应的最短路线如本例中查找从起始点到点的最短路线，如表中虚箭线所示，其路线为： 同样地，可以找到所有点的漫游路线3.7.6 结束语本文探讨的网络最短路的一种新算法混合步长网络漫游法，既具有TP标法的简易性，又具有负路权的特性，而且便于手工表上作业.对于计

35、算机算法的设计思路将进一步研究，且已获初步成果.3.7.7混合步长网络漫游最短路算法的进一步研究混合步长网络漫游最短路算法，阐述了混合步长网络漫游的算法原理、特点和具体的算法步骤本文将进一步就该方法的可行性定理、负回路的检测、最大漫游次数进行研究3.7.7.1 网络漫游可行性定理定理1 在一不存在负回路的任意路权网络中，若从起始点到任意一点有路可走，则通过网络漫游一定可以到达该点证明：因为 在混合步长网络漫游中，从起始点开始向外探索，且的初始路长为零，其余各点的初始路长为无穷大又第步的探索所得到的任意点j的路长为，其中，为当前漫游点，为点至之间直接路权每一步探索都可能改变其它各点的漫游路长，且

36、可能扩大已探索点的范围，即各个点的漫游路长是单调非增的又网络中不存在负回路，即从一点出发不可能再直接回到这一点最多经过步就可以探索到点，使其成为可漫游点，并最终成为已漫游点从而得到从起始点到该点的最短路及最短路长证毕3.7.7.2 负回路的检测问题上述网络漫游法可行性定理是在网络中不存在负回路的前提下得出的如果网络中存在负回路，则不论是手工表上作业法，还是计算机程序算法都会出现无限循环现象如果在进行网络漫游前不能确定网络中是否含有负回路，或者要确定这一事实要花太多的精力而跳过这一步，则在进行网络漫游的同时要进行负回路的检测，一旦检测到负回路的存在，则算法终止所谓负回路，就是在网络图中存在的一个

37、回路，且构成该回路的各弧的路权之和为负值如果从某点出发经过若干步直接的漫游之后又回到该点，则标志网络中存在负回路这里所说的直接漫游就是指下一个漫游点是由当前漫游点(所对应的点)直接计算路长所确定下来的，否则就是非直接漫游需特别注意的是，网络漫游法允许而且可能某一点的多次漫游，而并不存在负回路，但它必须是非直接的所以，当某点再次被漫游时，就要检测此点两次漫游之间的所有漫游是否都是直接的，若其中有一步是非直接的，则说明再次漫游该点是非直接的，否则，就是直接漫游，它表明网络中存在负回路下面以手工表上作业法漫游网络来演示负回路的检测在图1所示的网络图中存在着负回路用手工表上作业法漫游网络时应该能够发现

38、这种现象，否则就会无限漫游循环如表1所示，当点再次漫游时（表中第5步），就应该进行检测，判断是否存在从点又回到点的回路图1存在负回路的任意路权网络示意判断的方法是：从当前漫游点（表中第5步点）向上探索，当遇到大于当前漫游路长值时（包括计算行和选取行），横向搜索该行的漫游标记，遇到漫游标记时以同样的方法继续向上探索，如此进行下去如果能够到达当前漫游点的上一次漫游的位置（表1中第2步的），则找到了负回路；如果在探索的过程中从某一步的计算行转了方向，而找不到上一漫游点，则表明当前漫游为非直接漫游，即再次漫游该点并不表明存在负回路如表1中第5步点的再次漫游，从该点沿虚箭线向上探索，当探索到第2步时，从

39、计算行转了方向而找不到上一漫游点，所以点的再次漫游不能说明存在负回路再如表1中的第6步，点再次漫游，从该点沿实箭线向上探索并接连虚箭线，可以一直探索到第2步点的上一次漫游，它表明网络中存在以为顶点的负回路，这一探索的路线正是网络中负回路的逆向，即检测到负回路表1 混合步长网络漫游手工表上作业法的检测负回路功能示例3.7.7.3网络漫游次数定理定理2 （起始漫游定理）在不存在负回路的网络中，起始点的漫游次数为1证明： 起始点为漫游的出发点（记起始漫游为1次），且规定其漫游路长为零，其余各点的漫游都是本点的直接漫游如果从某一点再次回到起始点，则必然存在直接漫游负回路，而与假设矛盾在不存在负回路的网

40、络中，起始点的漫游次数一定为1定理3 （相邻漫游定理）网络中某顶点的最大漫游次数小于等于指向该点的各相邻点漫游次数之和证明： 在网络中某顶点得以漫游，则表明存在从起始点到该点的路一般而言，是可以漫游点，而、指向的点，则点的每次漫游势必经过、之一，即必有、之一先于点漫游点的最大漫游次数不会超过直接指向该点的各点漫游次数之和命题得证定理4 （最小漫游定理）若网络中某点存在可以漫游的相邻入度点，则该点的漫游次数至少为1证明：若网络中有弧，且为可漫游点，即存在从起始点到点的路，适得点得以漫游 也就必然存在从起始点到点的路，适得点得以漫游，即点至少漫游一次问题得证3.7.7.4结束语本文就作者所提出的“

41、混合步长网络漫游最短路算法”进行了进一步的探讨，研究了网络漫游法的可行性问题、负回路检测问题、最大漫游次数问题以及计算机算法原理但是，其理论还不十分完善，诸如最大漫游次数与图的结构之间的关系、各点均达到最大漫游次数时网络图的性质、任意两顶点之间漫游路长的算法等等许多问题还有待于进一步的研究第四章 最短路问题的应用4.1多条最短路算法的优化城市交通设施的建设远远落后于汽车的增长，由此造成的城市交通道路的堵塞和拥挤已成为世界各大城市面临的共同难题，其解决办法就是大力发展智能交通系统(ITS)， 改变现有的交通管理模式.ITS研究中的一项基础的研究工作就是如何确定最佳出行路线， 也就是要确定任意两点

42、间最短路问题.由于实际交通网络系统中存在着路段堵塞现象，所以仅仅给出任意两点间的一条最短路显然是不够的，应给出多条最短路供给ITS系统判别并选出最佳出行路线.4.1.1 算法的优选总结现有的算法就不难发现当今算法可分为两大类.一是枚举法，它通过依赖函数在与局部梯度相关的方向上移动来寻找局部最优，即先找到局部最优，再沿最佳允许方向处理函数.枚举法现在很多情况和规模上被认可，但效率很低，由于很多实际问题的网络都很大，以至于搜索一次需要的计算量很大，运算速度缓慢，但它能一次算出多条最短路，而这恰恰是我们所需要的；二是随机算法，它是利用随机技术来实现的.根据随机技术的不同又可分为遗传算法和模拟退火算法

43、.就目前较为热门的遗传算法而言， 它是一种基于自然选择原理和自然遗传机制的搜索(寻优)算法，将达尔文进化论中的“适者生存”与利用随机信息进行变化相结合. 说到随机性，遗传算法不是简单的随机走动，而是有效地利用、开发原有信息，并带着期望改善的性能去推测新的搜索点.因此在处理大型网络时比较有效，但它无法一次算出多条最短路.比较上述两类算法的优、劣之后，决定选取枚举法来进行优化后使用.因为找到多条最短路是最终的目标，随机算法虽能有效地处理大型网络，但却无法搜索到多条最短路，进行优化也比较困难；枚举法虽在处理大型网络时效率较低，但却能搜索到多条最短路，且优化也较容易些.枚举法中的算法又可分为求解一条最短路算法和求解多条最短路算法.文献2、3中均给出了在稀疏网络中一条最短路的优化，但都不适于求解多条最短路问题.在求解多条最短路算法中又包含两个算法，既二重扫除法(Shier)和推广的福劳