最短路径问题的算法分析及建模案例

最短路径问题的算法分析及建模案例一.摘要.............................................................................................................................................2二.网络最短路径问题的基础知识.................................................................................................32.1有向图................................................................................................................................52.2连通性.................................................................................................错误!未定义书签。2.3割集.....................................................................................................错误!未定义书签。2.4最短路问题........................................................................................................................6三．最短路径的算法研究................................................................................错误!未定义书签。3.1最短路问题的提出............................................................................................................63.2Bellman最短路方程.........................................................................错误!未定义书签。3.3Bellman-Ford算法的基本思想.......................................................错误!未定义书签。3.4Bellman-Ford算法的步骤...............................................................错误!未定义书签。3.5实例.....................................................................................................错误!未定义书签。3.6Bellman-FORD算法的建模应用举例...............................................错误!未定义书签。3.7Dijkstra算法的基本思想..............................................................................................63.8Dijkstra算法的理论依据..............................................................................................63.9Dijkstra算法的计算步骤..............................................................................................63.10Dijstre算法的建模应用举例......................................................................................73.11两种算法的分析..............................................................................错误!未定义书签。1.Diklstra算法和Bellman-Ford算法思想有很大的区别.........错误!未定义书签。Bellman-Ford算法在求解过程中，每次循环都要修改所有顶点的权值，也就是说源点到各顶点最短路径长度一直要到Bellman-Ford算法结束才确定下来。错误!未定义书签。2.Diklstra算法和Bellman-Ford算法的限制.............................错误!未定义书签。3.Bellman-Ford算法的另外一种理解...........................................错误!未定义书签。4.Bellman-Ford算法的改进...........................................................错误!未定义书签。摘要近年来计算机发展迅猛，图论的研究也得到了很大程度的发展，而最短路径问题一直是图论中的一个典型问题，它已应用在地理信息科学，计算机科学等诸多领域。而在交通路网中两个城市之间的最短行车路线就是最短路径问题的一个典型例子。由于最短路径问题在各方面广泛应用，以及研究人员对最短路径的深入研究，使得在最短路径问题中也产生了很多经典的算法。在本课题中我将提出一些最短路径问题的算法以及各算法之间的比较，最后将这些算法再应用于实际问题的建模问题中。关键词：计算机图论交通道路网最短路径A.Inthispaper,Computerdevelopingrapidlyinrecentyears,graphtheoryresearchalsohavebeengreatlydeveloped,andtheshortestpathproblemisatypicalproblemingraphtheory,ithasbeenappliedingeographicalinformationscience,computerscience,andmanyotherfields.Andinthetransportationnetworkoftheshortestroutebetweentwocitiesinisatypicalexampleoftheshortestpathproblem.Duetotheshortestpathproblemiswidelyusedinvariousaspects,andtheresearchersonthein-depthstudyoftheshortestpath,makeintheshortestpathproblemalsogeneratesalotofclassicalalgorithm.InthistopicI'llsuggestsomealgorithmandthealgorithmoftheshortestpathproblembetweenthecomparison,finallythealgorithmisappliedtothemodelingoftheactualproblemagain.Keywords:computergraphtrafficroadnetworkTheshortestpath前言最短路径问题是图论以及运筹学中的一个非常重要的问题，在生产实践，运输及工程建筑等方面有着十分广泛的应用。本文对图论中的最短路径问题进行分析，对其运算解法进行分析寻求比较快捷的模型解法；主要解决的是从某个顶点到其余各个顶点的最短路径问题。本文从Floyd算法以及Dijkstra算法两种算法入手，概述了这两种方法的原理，提出了求解最短路径问题的算法思想，并且对两种算法进行分析比较，提出改进的方法。一网络最短路径问题的基础知识图11.1图图G是一个（无向）图，其中有序二元组（V,E），V=｛1v，2v,...nv｝是顶点集，E=｛ije｝是集，ije是一个无序二元组{iv，jv}它表示该边连接的是顶点iv，jv。图1就是一个图。注释：图形的大小，位置，形状是无关紧要的。若ije={iv,jv}则称ije连接iv和jv；点iv和jv称为ije的顶点，iv和jv是邻接的顶点；如果两条边有公共的一个顶点，则称这两边是邻接的。1.2无环图定义：没有环的图称之为无环图。1.3简单图定义：没有环且没有重边的图称之为简单图。设G=（V,E）是一个简单图，则有|E|不大于|V|（|V|-1）/21.4完全图定义：若上式的等号成立那么该图中每对顶点恰好有一条边相连，则称该图为完全图。1.5有向图定义：一个有向图G是一个有序二元组（V,A），V=｛1v，2v，...,nv｝是顶点集，A=｛ija｝称为G的弧集，ija为有序二元组。称ija为iv连向jv的弧，ija为iv的出弧，jv的入弧；iv称为ija的得尾，jv称为aij的头；iv称为jv的前继，jv称为iv的后继。图2就是一个有向图。图21.6环定义：头尾重合的弧称为环。1.7简单有向图定义：没有环和重弧的有向图称为简单有向图。1.8完全有向图定义：设G=（V,E）是一个简单有向图，则|A|不大于|V|（|V|-1），若等号成立则称这样的图为完全有向图。1.9途径，迹，路定义：设图G=（V,E），若它的某些顶点与边可以排成一个非空的有限交错序列（0v，1e，1v,...ke,kv）,这里该途径中边互不相同，则称为迹；如果顶点互不相同，则称之为路。显然路必为迹，但反之不一定成立。1.10连通图定义：图G中如果存在一条从顶点iv到jv的途径，则称iv和jv是连通的。如果图G中任何两个顶点都是连通的，则称G是连通图。1.11有向途径定义：设有一个有向图G=（V,A），G中某些顶点与弧组成的非空有限序列（0v，1a，1v，2a，...，ka，kv）这里0v，...，kvV，iaA，且ia=（1iv，iv），则称它为从0v到kv的有向途径。类似的可定义有向迹，有向路，有向闭途径，有向闭迹，有向回路（圈）等。当G时简单有向图时，从0v到kv的一条有向途径可简记为（0v，...,kv）。二最短路问题定义：所谓最短路径是指如果从图中某一顶点（称为源点）到达另一顶点（称为终点）的路径可能不止一条，如何找到一跳有向路径使得沿这条路径上各弧的权值总和最小。2.1最短路问题的提出某旅客要从杭州乘飞机前往奥地利的萨尔斯堡，因为他害怕乘坐飞机，因此要选择一条航线，使得在空中飞行的时间尽可能的少。如何选择航线以达到要求。为此构造一个无向网络总可以化成有向网络。设G=（V,A,w）是一个有向网络，p为G中一条有向路，称w（P）=Paaw)(为路径p的路长。现找网络中一条从指定顶点vi到另一个指定顶点vj的最短有向路径。三最短路径算法研究3.1Dijkstra算法3.11Dijkstra算法的基本思想对网络中每个顶点赋一个标号，用来记录从1v顶点到该顶点的最短路的长度（称为永久标号）或最短长度的上界（称为临时标号）。算法开始时，只有顶点1v被赋予永久标号1v=0，其他顶点iv赋予临时标号ijjwu。一般的，算法在被临时标号的顶点中寻找一个顶点kv，其临时标号ku最小，然后将kv赋予永久标号ku，并且对其余临时标号的顶点vj按照方式},m