利用lingo求解几种有向图最短路问题

《利用lingo求解几种有向图最短路问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、利用LinGo求解几种有向图最短路问题襄樊职业技术学院学报第卷第期：・/双月刊年月利用求解儿种有向图最短路问题刘淋福建交通职业技术学院，福州摘要:木文对几种有向赋权图的最短路长和路径采用软件对其求解,并分析了用解法的简便Z处和如何处理赋权有向图中的负权问题。对解决此类问题提供了一种新的途径。关键词：；有向图;最短路中图分类号:文献标识码：文章编号：？？？最短路径问题是图论研究屮的一个经典算法问首先，我们介绍常用的算法。设某图中题，旨在寻找图由结点和路径组成的中两结点之各个顶点定义为，，从顶点到顶点的赋权定义为方法的基木思想是在；；$的间的最短路径。最短路径通常归为三类:第

2、一，单源情形下，从岀发，逐步地向外探寻最短路。执行过最短路径问题:包括确定起点的最短路径问题与确定终点的最短路径问题。确定终点的最短路径问题程中，与每个点对应，记录下一个数称为这个点的与确定起点的问题相反，该问题是已知终结结点，求标号，它或者表示从到该点的最短路的权称为最短路径的问题。在无向图屮该问题与确定起点的标号，或者是从到该点的最短路的权的上界称问题完全等同，在有向图中该问题等同于把所有路为标号，方法的每一步是去修改标号，并且把某径方向反转的确定起点的问题。第二，确定起点和个具标号的点改变为具标号的点，从而使图中终点的最短路径问题：即已知起点和终点，求两结点具标号的

3、顶点数多一个，这样，至多经过~步，就之间的最短路径。第三,全局最短路径问题:求图中可以求出从到各点的最短路。所有的最短路径。我们引个例子说明算法的基本思想。图本文探讨的是上述的第二种，确定起点和终点所示的单行线交通图，每弧旁的数字表示通过这条的最短路径问题。对于此类最短路问题，口前最常单行线所需要的费用。现在某人从岀发，通过这个用的最短路径算法有：算法、算法、交通网能够到去,求使总费用最小的旅行路线。图？算法、和中，，因为所有的・・2,故有，。・算法。如果应用算法来实现的最短路的话，要求对编程比较熟悉，可以用语言实现,也可以等数学软件中实现。但是对于大多人来说，只需找到一

4、种简单易懂的解题工具，而且望这一丁具能解决最短路的各种问题。本文就是介绍用软件来解决最短路问题。虽然文中介绍的是有向图的最短路，但所有程序同样适用于各类无向图。众所周知，软件是用来求解线性和非线性优化问题的简易工具。内置了一种建立最优化模型的语言，可以简便地表达大规模问题，利用？图单行线交通图高效的求解器可快速求解并分析结果。这里我们这时，。是具标号的点。现在开查从。发出的三条弧，，，，和，，如果某人从。出发沿，用它来解决最短路问题，并能得出最短路所经过的路径。到达：，这时需要。。：的单位费用；如果他收稿日期:？?作者简介:刘淋一，女，福建福、人。讲师，研究方向:应用数学

5、。刘淋从，出发沿。，到达。，这时需要，。的单例：求下图图所示赋权有向图屮从。到各位费用；类似地，若沿，达，需要。，点的最短路。的单位费用。程序如下：??????????一因，，，，，，可以断言，他从岀发到所需要的最小费用必定是单位,即从到的最短路是,,,,・这是因为从到的任一条路，如果不是,，则必是先从沿。，达：，或者沿，到达，，而后再从或，去，但如上所说，这时候他己需要单位或者单位的费用，不管他如何再从：或到达，所？？？994-9999"•••••••需要的总费用都不会比少因为所有的M。因而推知，，这样就可以使变成具标号的点。图赋权有向图现在考查从及指向其余点的弧，由

6、上已知，：从出发，分别沿。，、。，到达：，。，需要单位'/,,,,,,,/•,或单位的费用，而从出发沿，到达,所需要，/的费用是，单位。，，，因，】，，】，，十，，，，，，，，，，，，基于同样的理由可以断言，从到，的最短路是，，/:;,,,,这样乂可以使点变成具标号的点。如此重复这个过程，可以求出从，到任一点的最：短路。~?那么如果图的顶点数比较多，路线相对复杂,？?用法计算量就很大。本文采用软件来对最短路进行求解，程序简单，适用度大。下面用；来对三个例子进行分析求解。？，；例：对上文图的旅行路线进行求解。程序如下：::,,,程序分析:取消对的符号限制，即，，，，，，可取

7、正、负和零。，，，/:;・9■•哇9••■••9•,口，.一9••，»,?，程序分析：表示从城市到其他城市的最优路，市之间道路的长具体径；表示两城市之间的道路；表示上述两城数据；最短路的计算公式。・，，・程序运行结果：表示从到的最短，哇9