资源描述：
《利用LinGo求解几种有向图最短路问题.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、襄樊职业技术学院学报第9卷第6期doi:10.3969/j.issn.1671-914X.2010.06.025双月刊2010年11月利用LinGo求解几种有向图最短路问题刘淋（福建交通职业技术学院，福州350007）摘要：本文对几种有向赋权图的最短路长和路径采用Lingo软件对其求解，并分析了用Lingo解法的简便之处和如何处理赋权有向图中的负权问题。对解决此类问题提供了一种新的途径。关键词：Lingo；有向图;最短路中图分类号：0157文献标识码：A文章编号：1671-914X（2010）06-0025-03最短路径问题是图论研究中的一个经典算
2、法问首先，我们介绍常用的Dijkstra算法。设某图中题，旨在寻找图（由结点和路径组成的）中两结点之各个顶点定义为V（nn=1,2…i…），从顶点i到顶点j的间的最短路径。最短路径通常归为三类：第一，单源赋权定义为wij。Dijkstra方法的基本思想是在wij≥0的最短路径问题：包括确定起点的最短路径问题与确情形下，从vs出发，逐步地向外探寻最短路。执行过定终点的最短路径问题。确定终点的最短路径问题程中，与每个点对应，记录下一个数（称为这个点的与确定起点的问题相反，该问题是已知终结结点，求标号），它或者表示从vs到该点的最短路的权（称为P最短路径
3、的问题。在无向图中该问题与确定起点的标号），或者是从vs到该点的最短路的权的上界（称问题完全等同，在有向图中该问题等同于把所有路为T标号），方法的每一步是去修改T标号，并且把某径方向反转的确定起点的问题。第二，确定起点和一个具T标号的点改变为具P标号的点，从而使图中终点的最短路径问题：即已知起点和终点，求两结点具P标号的顶点数多一个，这样，至多经过p-1步，就之间的最短路径。第三，全局最短路径问题：求图中可以求出从vs到各点的最短路。所有的最短路径。我们引个例子说明Dijkstra算法的基本思想。图本文探讨的是上述的第二种，确定起点和终点1所示的单
4、行线交通图，每弧旁的数字表示通过这条的最短路径问题。对于此类最短路问题，目前最常单行线所需要的费用。现在某人从vs出发，通过这个用的最短路径算法有：Dijkstra算法、A*算法、交通网能够到v8去，求使总费用最小的旅行路线。图Floyd-Warshall算法、Johnson算法和Bi-DirectionBFS1中，s=1,因为所有的wij≥0，故有d(v1,v1)=0.算法。如果应用算法来实现的最短路的话，要求对编程比较熟悉，可以用C语言实现，也可以在matlab等数学软件中实现。但是对于大多人来说，只需找到一种简单易懂的解题工具，而且希望这一工
5、具能解决最短路的各种问题。本文就是介绍用Lingo软件来解决最短路问题。虽然文中介绍的是有向图的最短路，但所有程序同样适用于各类无向图。众所周知，Lingo软件是用来求解线性和非线性优化问题的简易工具。Lingo内置了一种建立最优化模型的语言，可以简便地表达大规模问题，利用Lin-图1单行线交通图go高效的求解器可快速求解并分析结果。这里我们这时，v1是具P标号的点。现在开查从v1发出的三用它来解决最短路问题，并能得出最短路所经过的条弧，(v1,v2)，(v1,v3)和(v1,v4),如果某人从v1出发沿(v1,v2)路径。到达v2，这时需要d(v
6、1,v1)+w12=6的单位费用；如果他收稿日期：2010-08-10作者简介：刘淋（1979-），女，福建福州人。讲师，研究方向：应用数学。25刘淋从v1出发沿(v1,v3)到达v3，这时需要d(v1,v1)+w13=3的单例2：求下图（图2）所示赋权有向图中从V1到各位费用；类似地，若沿(v1,v4)到达v4，需要d(v1,v1)+w14=1点的最短路。的单位费用。程序如下：因min{d(v1,v1)+w12,d(v1,v1)+w13,d(v1,v1)+w14}=d(v1,v1)+w14=1可以断言，他从v1出发到v4所需要的最小费用必定是1单
7、位，即从v1到v4的最短路是(v1,v4),d(v1,v4)=1,这是因为从v1到v4的任一条路P,如果不是(v1,v4)，则必是先从v1沿(v1,v2)到达v2，或者沿(v1,v3)到达v3，而后再从v2或v3到v4去，但如上所说，这时候他已需要6单位或者3单位的费用，不管他如何再从v2或v3到达v4，所需要的总费用都不会比1少（因为所有的wij≥0）。因而推知d(v1,v4)=1，这样就可以使v4变成具P标号的点。现在考查从v1及v4指向其余点的弧，由上已知，图2赋权有向图从v1出发，分别沿(v1,v2)、(v1,v3)到达v2，v3，需要6单
8、位sets:或3单位的费用，而从v4出发沿(v4,v6)到达v6，所需要CITIES/v1,v2,v3,v4,v5,v6,
