资源配置中的最短路

1、关于资源配置中的最短路问题 摘 要：网络购物在人们的日常生活中扮演着越来越重要的角色，网购蓬勃发展的同时刺激了社会物流业的快速崛起，卖家如何选择出一条最短物流途径进行商品配送，降低运送成本，是十分重要的。本文针对如何求解资源配置中的最短路径问题,主要介绍了算法和算法以及它们各自的优化算法，从而掌握求解最短路径的这两种基本方法。最短路问题是对一个赋权的有向图 D 中指定的两点 Vs 和 Vt 找到一条从 Vs 到 Vt 的路,使得这条路上所有弧的权数和总和最小, 这条路即为从 Vs 到 Vt 的最短路, 这条路上所有弧的权数的总和为从 Vs 到 Vt 的距离。在实际工作中， 最短路问题很常见。求

2、解一般最短路问题， 可用图和网络的方法或动态规划的方法， 但是不同的解法各有其要求及特点。 通过两个问题的具体解法探讨了动态规划方法与图与网络的 Dijkstra 算法各自的特点及适用范围和要求。 关键词：资源配置；最短路；算法；算法；优化 Abstract: Shopping on the internet is playing a more and more important role in our daily life. This scene stimulates the effective developments of the logistics industry at

3、the same time. So it is very crucial for sellers to pick up a reasonable delivery way to save more delivery costs . The paper mainly introduces the Dijkstra algorithm and the Floyd algorithm, we should learn them well and use them to find the shortest path.Key words: resource; allocation 

4、Dijkstra algorithm; Floyd algorithm ; optimization1 前 言21世纪是一个社会各行业获得飞速发展的时代，无论是政治，经济，科技，文化领域都取得了显著进步。我们以科技发展为例，日新月异的科技进步促进了网络的发展，高效便捷的网络正在潜移默化地改变我们的生活。网络走进了千家万户，丰富的网络资源开阔了我们的视野，提高了我们的工作效率。如今，网购也成为一种非常普遍的现象。网购给我们的生活带来了巨大的便捷，我们足不出户就可以享受送货上门的优待。网购在被大众广泛接受的同时，也带动了物流业的快速发展。卖家在向买家送货的过程中，需要合理分析多种物流途径，从中选择

5、一条最短路径，从而降低运输成本，节约配送时间，实现资源配置的最优化。最短路作为图与网络技术研究中的一个经典问题一直在工程规划地理信息系统通信和军事运筹学等领域有着十分广泛的应用，对该问题求解算法的设计和改进研究有着重要的理论和应用价值目前，关于最短路问题的研究已有较多结果传统的最短路算法主要有Floyd算法1和Dijkstra算法2等 其中Floyd算法主要用于计算所有节点对之间的最短路；而Dijkstra算法是一种用于计算从一个源节点到其所有宿节点最短路的高效算法本文主要介绍图论中求最短路径方法的算法和算法，通过深入分析两种算法的基本思想，从而掌握求解最短路径的这两种经典算法。2 问题的提出

6、如图1-1，现有卖家从发货地（记为节点0）向买家所在地（记为节点3）送货，可选择的物流途径中包含中转站（记为节点1,2,4,5）。图中已经给出了每两个节点之间的距离与路径方向，卖家希望选择合适的中转站，使从发货地到买家收货地的物流路线最短。即图1-1中，从节点0到节点3的最短路径。这就是一个典型的最短路问题。3 定义与符号说明（1） 有序积（和是两个集合）。（2） 无序积，其中（3） 图-定义为一个偶对，记作，其中 是一个集 合，其中的元素称为顶点；是无序积中的一个子集合，其元素称为边。（4）带权有向图-定义为一个偶对，其中 是一个非空集 合，其元素称为顶点；是有序积的一个子集,其元素称为弧。

7、（5）关联-图中一条边的端点称为与这条边关联。（6）节点的度-指和该节点相关联的边的数目。（7）弧的权重-图中每条边的长。（8）0-图的起始点（9）-图中的各个节点（10）-连接图中节点和节点之间弧的权重（11）-图中节点的临时性标号（12）-图中节点的永久性标号（13）-图中从起始点0到节点最短路权的上界（14）-图中从起始点0到节点最短路权（15）-图1-1中连接节点与节点的弧的长度（16）-图1-1中节点到节点的最短距离（17）-连接节点和节点的弧（18）-连接节点和节点的中间节点的数目（19）-图1-4中入度大于0的节点集合（20）-图的顶点数4 算法介绍4.1 求最短路算法4.1.1

8、 算法思想算法适用于加权有向图或无向图中单源点到其他顶点的最短路径问题，是按长度递增的次序来产生最短路径的算法。我们以带权（规定权重均为非负值，即）有向图为例加以分析。先给带权图的每一个顶点记一个数（称为标号）-临时标号（简称标号）或永久性标号（简称标号）。标号标示从图起始点0到这一节点最短道路长的上界，标号则是从起始点0到这一点的最短道路长。算法的每一步都把某个点的标号改为标号。这样一旦终点得到标号，算法停止。如果寻求从图中的起始点0到某一点的最短路径，则最多经过步算法停止。4.1.2 算法步骤 初始时，起始点0,.其他节点临时性标号记为+，即 若节点点是刚得到标号的点，考虑图中与节点相连的

9、弧且节点是标号。对节点的标号进行如下更改：比较所有具有标号的点，把最小者改为标号。当存在两个以上最小者时，可同时改为标号； 重复上述过程，直到得出终点的标号； 将上面得到标号节点的次序反向，就是图中从起始点0到终点的最短路径。 算法的正确性是显然的。因为在任一步，设中每一点的标号是从图的起始点0到该节点的最短道路长（开始，这个假设显然是对的），下面只要说明是从起点0到节点的最短路径。实际上，任一条从起点0到节点的道路，若通过标号的第一个节点是，而的话，由于所有边长为非负，则这种道路长不会比小，所以算法成立。4.2 求最短路算法算法主要解决单源点物流最短路径问题。那么如何求出图中任意节点之间的最

10、短路径。如果使用算法，可以将每一个节点当作起始点分别求其到各节点的最短路径。操作中我们可以发现这个过程较为繁琐，耗时长。针对这个问题，我们引出算法，该算法适用于无向图和有向图，能够一次性求得图中任意节点间的最短路径，下面我们主要探讨它在带权有向图的应用情况。4.2.1 算法思想对于图中任意节点间的最短路径问题，我们思考从节点到节点的最短距离路径只有两种可能，即节点与直接相连和节点与通过中间节点相连。可以看出算法是研究节点与之间插入节点的情况的算法，故又形象地称其为插点法。4.2.2 算法步骤 令图中（是图中节点与之外剩余节点的数目），比较与的值； 若有，表示从节点出发经过中间节点再到节点的距离

11、要比原来的节点直接到的距离短，所以把改为， 重复上述过程，当所有的都查完了，就是目前节点到的最短距离。5 算法的应用5.1 算法应用 例1 用算法求解图1-1中的最短路问题。解 首先记，该问题中各条弧的权重即为图1-1中所标出的两节点间线段的长度。 ：图1-1中与节点0相连的弧是（0,2）和（0,3），且节点2， 3 均为标号。修改这两个节点的标号： ：在所有标号中（），因为最小， 所以，令 ：图1-1中与节点2相连的弧是（2,1）和（2,5），且节点1，5均为标号。修改这两个节点的标号： ：在当前所有标号中，最小，所以，令 ：图1-1中与节点5相连的弧是（5,3）和（5,4），且节点3,4均

12、为标号。修改这两个节点的标号： ：在所有标号中（即）,因为最小，所以，令到目前为止，我们从图1-1中起始点0出发得出终点3的标号。将以上得到标号节点的次序反向就可以得到从起始点0到终点3的最短路径。具体如下：因为节点3与节点5永久性标号的差是10恰等于弧（5,3）的长度。所以，退回到节点5.而节点5与节点2的永久性标号差是7恰等于弧（2，5）的长度。所以，退回到节点2.最后退回到起点0.故得到从起点0到节点3的最短路径是：0253，长度为22. 5.2 算法应用例2 用算法求解图1-1中节点1到节点3的最短路径。 解 判断从节点1出发是否可以不通过其他节点直接到达节点3.由图1-1可以看出节点

13、1与节点3不直接相连，必须通过图中其他节点将它们连接起来。 判断从节点1出发是否可以只通过一个节点然后到达节点3.观察图1-1得到符合条件的分别是中间节点0和节点4. 路径一：103. 路径二：143. 判断从节点1出发是否可以中途经过两个节点最终到达节点3.观察图1-1得到没有符合条件的中间节点。 判断从节点1出发是否可以中途经过三个节点最终到达节点3.观察图1-1得到符合条件的一组中途节点0，节点2，节点5.路径三：10253. 判断从节点1出发是否可以途中通过四个节点最终到达节点3.观察图1-1得到符合条件的一组中途节点0，节点2，节点5，节点4.路径四：102543. 目前为止，所有节

14、点全部讨论完毕。比较路径一，路径二，路径三，路径四，得到节点1到节点3的最短路径为路径二：143. 6 算法优化6.1 优化算法算法是典型最短路算法之一，主要特点是以带权有向图起始点为中心向外层层扩展，直到扩展到终点为止。要求图中每条弧权值均为非负。算法虽然能够得出最短路径的最优解，但由于随着带权有向图中顶点数量的增加，计算步骤也会逐渐增多，大大降低计算效率。针对算法的不足之处，这里提出一种的优化算法。6.1.1 优化算法思想我们在网购过程中注意到卖家是按收货地分区域配送货物的，并不是按照唯一的路径送货。这一现象启发我们在用算法求最短路径的过程中，也许并不需要把每个点都讨论一遍，而只需要讨论某

15、些关键点。我们知道几何意义上两点之间线段最短。因此，起始点0到指定节点的最短路径一定在直接连接起始点与终点的弧的附近。我们以这条弧为界来划分图，分别计算出每个子图的最短路径，最后加以比较分析得出结论。6.1.2 优化算法的应用例3 我们在图1-1中使用优化算法求起点0到终点3的最短路径。解 将图1-1进行划分。在图1-1中可以看到起始0与终点3由弧（0,3）直接相连。故它们之间的最短路径一定在这条弧附近。所以以这条弧为界将图1-1划分成三个子图，分别为图1-2、图1-3和图1-4.841423030 图 1-2304403183510710552图 1-4图 1-3由这三个子图，可以马上确定出

16、源点0到终点3之间的最短路径在图1-3中，是路径0253，权为22.可以看出优化后的算法中划分子图的过程直观易懂，算法步骤也更为简单，确实有效提高了算法效率。6.2 优化算法算法过程容易理解，可以求出图中任意两个节点之间的最短路径。但是每次讨论图中任意两个节点间的最短路径都要将其余所有节点考虑一遍（插点法），这样会耗费大量运算时间，因此我们介绍一种的优化算法。6.2.1 优化算法思想在使用算法进行插点之前，我们先规定一个集合，它表示所有入度不为0的节点集合。然后后续的插点过程就只在集合中选点，直到成为空集，求得题目中要求的两节点间的最短路径。这样就要求每次经过的中间点入度必须大于0，裁剪掉了不

17、可能经过的中间节点，避免了无谓的计算，节省了运算时间。6.2.2 优化算法的应用2378 1251003614图 1-4例4 用优化算法求图1-4中节点0到节点4的最短路径。解 ：节点0与节点4之间没有直接的弧相连，考虑插入剩余节点（节点1、节点2和节点3）。 ：节点1,节点2，节点3中入度大于0的节点集合=（节点1,节点2）。 ：在节点0与节点4之间只插入节点1，路径一：014. ：在节点0与节点4之间插入节点1和节点2，路径二：0124. 故得到节点0与节点4之间最短路径为 路径一：014. 在上述求解过程中可以看出优化算法相比未优化前的方法减少了中间入度为0的节点3的讨论。对于节点数比较

18、多的带权有向图，在求解图中任意节点间的最短路径时，优化算法能够更加显示出它的算法优越性，提高计算效率。7 结束语以上我们主要讨论了针对求节点间最短路径的算法和算法，通过介绍两种算法，了解了它们各自的算法核心思想，也探讨了在实际问题中两种算法存在的不足之处，并加以简单优化思维。这次研究不仅让我们深入了解了算法和算法，体会这两种经典算法的巨大魅力，也拓展了我们的思维，优化处理环节确实能够让我们感受到数学学科的强大生命力与价值，这是我们每一个数学研究者都引以为傲的地方。数学来源于生活，服务于生活。生活中处处体现着数学思想，数学让我们享受更加智慧的生活。最短路径问题涉及到我们生活的方方面，算法和算法为我们提供了有利的解决途径。特别是物流业要理解两种算法的基本思想并能够简灵活应用于实际操作中，进而实现资源的高效配置。现代社会中充满了讨论最优化的思想理念，无论是企业市场还是事业单位都在不断地追求如何使用最少的投资达到最大的收益。可见，研究最优问题是十分有意义与价值的。最优化理念不仅可以节约资源，降低成本，实现最大限度的收益；进而达到资源的最大限度利用，有利于建成资源节约型，环境友好型的和谐社会。参考文献：1 阮洁,钟宝荣.算法在物流配送运输中的最短路径优化研究J.计算机光盘