【最小费用最大流在路径规划中的应用探究17000字（论文）】

最小费用最大流在路径规划中的应用研究摘要流通领域中，许多物流配送企业借助外部经济的发展，实现了规模扩张与快速发展，但对如何控制成本，提高运营效率的迫切性并不强。现在随着经营环境的变化，物流需求量更大，客户、网络更复杂，对服务的要求更多样化。但面临的竞争更加激烈，不管是从事跨区域配送还是城市配送，首先需要考虑顾客服务水平，赢得客户的认可，然后考虑配送运营的成本问题，因而如何创新物流服务，提高运营效率和控制日常运营成本成为每个配送企业需要时刻思考的问题。传统的基于经验的方法，在企业规模有限，客户数量不是非常多，配送网络相对简单的情况下，只要员工和管理者技能过关，执行力好，都应该能够较好地完成配送任务，获得企业的发展。但是随着销售区域扩大，客户数量的不断增加，客户需求持续增长，配送业务量大增，配送周期缩短，配送线路更复杂，并且需求的随机性、变动性加大，光凭经验和手工安排，已无法做到配送计划的优化，必须借助于统计分析、利用数学模型和智能算法，才能获得较好的配送计划，节省时间，提高效率。本文就是针对这些问题，从企业应用的角度，提出先合理划分配送区域，再优化配送路线的方法，从而达到降低成本，提高竞争力的目标。关键词：最小费用；最大流；路径规划目录7941引言 529517第一章基本知识 564851.图论基本知识 5323072.网络流基本知识 912165第二章最小费用流问题 11325761最小费用流问题 1168252最小费用流问题的模型建立 12183193最小费用最大流介绍 1499033.1最小费用最大流的模型 14282303.2最小费用最大流的算法 1525931第三章：路径规划 15247841路径规划介绍 15119602路径规划算法 157433第四章最小费用最大流算法在路径规划中的应用 17157881.最短路算法 17322451.1问题引入 17265441.2.Dijkstra算法 17141181.3.Floyd算法 19157451.4.Bellman-Ford算法 23154041.5.SPFA算法 29315212.

配送区域动态优化及其方法 30319543基于改进蚁群算法的分区线路优化方法 3211709总结 3325587参考文献 34

引言近几十年,组合优化和图论,广义上来讲作为组合数学的完整研究领域,经历了飞速的发展。网络理论是图论与数学规划相结合的产物,近二十年来发展十分迅速,应用也非常广泛。例如在生产一分配系统、交通运输系统、通讯系统、财贸系统、军事后勤系统、管道网络系统和电网系统中都得到了很好的应用,因此对它的研究有非常重要的意义。线性规划的一类重要应用是网络最优化问题或称网络规划,网络流在生产和社会实践中有着广泛的应用,是组合优化及图论中被广泛研究的问题领域之一,横跨多个学科的研究,包括应用数学、计算机科学、工程学、管理学以及运筹学等等。最小费用流是最为基本的网络流模型,它是指在一个给定的网络中求一个从发点到收点的流值为某一给定常数的流,使其费用最小。最小费用流问题是一个常用的组合优化问题,对于该模型已有丰富的研究成果,在理论和实践中都有着广泛的应用,许多实际的网络流问题如运输问题、最短路问题、最大流问题、指派问题等问题都可以转化为最小费用流问题求解。但是随着人类活动和生产过程的日益复杂,新问题不断出现,这对原有的网络模型构成了挑战,也为网络流的进一步发展提供了良好的机遇。第一章基本知识1.图论基本知识图论〔GraphTheory〕是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。一些由结点及边构成的图称为线图。在线图中，结点的位置分布和边的长短曲直都可以任意描画，这并不改变实际问题的性质。我们关心的是它有多少个结点，在哪些结点间有边相连，以及整个线图具有的某些特性。有向图：每条边都是有向边的图.

无向图：每条边都是无向边的图.

混合图：既有有向边又有无向边的图.

自回路：一条边的两端重合.

重数：两顶点间若有几条边,称这些边为平行边,两顶点a,b间平行边的条数成为（a,b）的重数.

多重图：含有平行边的图.

简单图：不含平行边和自回路的图.重要定理：定理5.1.1设图G是具有n个顶点m条边的有向图,其中点集V={v,v,….,v}deg+(vi)=deg-(vi)=m定理5.1.2设图G是具有n个顶点m条边的无向图,其中点集V={v,v,v,……,v}deg(vi)=2m推论在无向图中,度数为积数的顶点个数为偶数.通路和富权图的最短通路1通路和回路基本概念：通路的长度：通路中边的条数.回路：如果通路中始点与终点相同.简单通路：如果通路中各边都不相同.基本通路：如果通路中各顶点都不相同.显然（基本通路一定是简单通路,但简单通路不一定是基本通路）可达：在图G中如果存在一条v到d通路则称从v到d是可达.连通：在无向图中如果任意两点是可达的,否则是不连通的.强连通：在有向图中如果任意两点是互可达的.单向连通：在有向图中如果存在任意两点的通路.弱连通：在有向图中如果其底图是连通的.权：在图的点或边上表明某种信息的数.赋权图：含有权的图.赋权图的最短通路问题的算法：先求出到某一点的最短通路,然后利用这个结果再去确定到另一点的最短通路,如此继续下去,直到找到到的最短通路为止.指标：设V是图的点集,T是V的子集,且T含有z但不含a,则称T为目标集.在目标集T中任取一个点t,由a到t但不通过目标集T中其它点所有通路中,个边权和的最小者称为点t关与T的指标记作DT(t).图和矩阵住意两个的区别：A·A中元素的意义：当且仅当a和a都是1时,aa=1而a和a都为1意味着图G中有边(v,v)和(v,v).于是可得如下结论：从顶点v和v引出的边,如果共同终止于一些顶点,则这些终止顶点的数目就是b的值；特别对于b,其值就是v的出度.A·A中元素的意义：当且仅当a和a都为1时,aa=1,这意味着图中有边(v,v)和(v,v).于是的得如下结论：从某些点引出的边,如果同时终止于v和v,则这样的顶点数就是的值.特别对于b,其值就是的v入度.幂A中元素的意义：当m=1时,a中的元素=1,说明存在一条边(v,v),或者说从v到v存在一条长度为一的通路.A中元素a表示从v到v的长度为m的所有通路的数目.

欧拉图主要定义：如果图中存在一条通过图中个边一次且仅一次的回路,则称此回路为欧拉回路,具有欧拉回路的图称为欧拉图.如果图中存在一条通过图中各边一次且仅一次的通路,则称此回路为欧拉通路,具有欧拉通路的图称为半欧拉图.主要定理：一个无向连通图是欧拉图的充要条件是图中各点的度数为偶数.一个无向连通图是半欧拉图的充要条件是图中至多有两个奇数度点.设图G是有向连通图,图G是欧拉图的充要条件是图中每个顶点的入度和出度相等.设图G是有向连通图,图G是半欧拉图的充要条件是至多有两个顶点,其中一个顶点入度比它的出度大1,另一个顶点入度比它的出度少1；而其他顶点的入度和出度相等.[1]哈密顿图主要定义：如果图G中存在一条通过图G中各个顶点一次且仅一次的回路,则称此回路为图的哈密顿回路；具有哈密顿回路的图称为哈密顿图.如果图G中存在一条通过图G中各个顶点一次且仅一次的回路,则称此回路为图的哈密顿回路；具有哈密顿回路的图称为哈密顿图.

主要定理：设图G是哈密顿图,如果从G中删去个p顶点得到图G’,则图G’的连通分支数小于等于p.设图G是具有n个顶点的无向简单图,如果G中任意两个不同顶点的度数之和大于等于n-1,则具有哈密顿通路,即G是半哈密顿图.设图G是具有n个顶点的无向简单图,如果G中任意两个不同顶点的度数之和大于等于n,则G具有哈密顿回路,即G是哈密顿图.

注意!一条无向边可以用一对方向相反的有向边代替,因此一个无向图可以用这种方法转化为一个有向图.

定向图：如果对无向图G的每条无向边指定一个方向由此得到的有向图D.称为的G定向图.

底图：如果把一个有向图的每一条有向边的方向都去掉,得无向图G称为的D底图.

逆图：把一个有向图D的每条边都反向由此得到的图称为D的逆图.

赋权图：每条边都赋上了值.

出度：与顶点相连的边数称为该定点的度数,以该定点为始边的边数为出度.入度：以该定点为终边的边数为入度.

特殊!度数为零的定点称为孤立点.度数为一的点为悬挂点.

无向完全图：在阶无向图中如果任何两点都有一条边关连则称此图是无向完全图.Kn

完全有向图：在阶有向图中如果任意两点都有方向相反的有向边相连则称此图为完全有向图.

竟赛图：阶图中如果其底图是无向完全图,则程此有向完全图是竟塞图.

注意!n阶有向完全图的边数为n的平方；无向完全图的边数为n(n-1)/2.

下面介召图两种操作：①删边：删去图中的某一条边但仍保留边的端点.

②删点：删去图中某一点以及与这点相连的所有边.

子图：删去一条边或一点剩下的图.

生成子图：只删边不删点.

主子图：图中删去一点所得的子图称的主子图.

补图：设为阶间单无向图,在中添加一些边后,可使成为阶完全图；由这些添加边和的个顶点构成的图称为的补图.

2.网络流基本知识对一个流网络G=(V,E)，其容量函数为c，源点和汇点分别为s和t。G的流f满足下列三个性质：容量限制：对所有的u，v∈V，要求f(u,v)<=c(u,v)。反对称性：对所有的u，v∈V，要求f(u,v)=-f(v,u)。流守恒性：对所有u∈V-{s,t}，要求∑f(u,v)=0(v∈V)。容量限制说明了从一个顶点到另一个顶点的网络流不能超过设定的容量，就好像是一个管道只能传输一定容量的水，而不可能超过管道体积的限制；反对称性说明了从顶点u到顶点v的流是其反向流求负所得，就好像是当参考方向固定后，站在不同的方向看，速度一正一负；而流守恒性说明了从非源点或非汇点的顶点出发的点网络流之和为0，这有点类似于基尔霍夫电流定律，且不管什么是基尔霍夫电流定律，通俗的讲就是进入一个顶点的流量等于从该顶点出去的流量，如果这个等式不成立，必定会在该顶点出现聚集或是枯竭的情况，而这种情况是不应该出现流网络中的，所以一般的最大流问题就是在不违背上述原则的基础上求出从源点s到汇点t的最大的流量值，显然这个流量值应该定义为从源点出发的总流量或是最后聚集到t的总流量，即流f的值定义为|f|=∑f(s,v)(v∈V)。[2]a.在给定的流网络G=(V,E)中，设f为G中的一个流，并考察一对顶点u，v∈V，在不超过容量c(u,v)的条件下，从u到v之间可以压入的额外网络流量，就是(u,v)的残留容量，就好像某一个管道的水还没有超过管道的上限，那么就这条管道而言，就一定还可以注入更多的水。残留容量的定义为：cf(u,v)=c(u,v)-f(u,v)。[3]而由所有属于G的边的残留容量所构成的带权有向图就是G的残留网络。下图就是上面的流网络所对应的残留网络：残留网络中的边既可以是E中边，也可以是它们的反向边。只有当两条边(u,v)和(v,u)中，至少有一条边出现在初始网络中时，边(u,v)才会出现在残留网络中。下面是一个有关残留网络的定理，若f是G中的一个流，Gf是由G导出的残留网络，f'是Gf中的一个流，则f+f'是G中一个流，且其值|f+f'|=|f|+|f'|。证明时只要证明f+f'这个流在G中满足之前所讲述的三个原则即可。在这里只给出理解性的证明，可以想象如果在一个管道中流动的水的总流量为f，而在该管道剩余的流量中存在一个流f'可以满足不会超过管道剩余流量的最大限，那么将f和f'合并后，也必定不会超过管道的总流量，而合并后的总流量值也一定是|f|+|f'|。[4]

b.增广路径p为残留网络Gf中从s到t的一条简单路径。根据残留网络的定义，在不违反容量限制的条件下，G中所对应的增广路径上的每条边(u,v)可以容纳从u到v的某额外正网络流。而能够在这条路径上的网络流的最大值一定是p中边的残留容量的最小值。这还是比较好理解的，因为如果p上的流大于某条边上的残留容量，必定会在这条边上出现流聚集的情况。所以我们将最大量为p的残留网络定义为：cf(p)=min{cf(u,v)|(u,v)在p上}。而结合之前在残留网络中定理，由于p一定是残留网络中从s到t的一条路径，且|f'|=cf(p)，所以若已知G中的流f，则有|f|+|cf(p)|>|f|且|f|+|cf(p)|不会超过容量限制。c.流网络G(V,E)的割(S,T)将V划分成为S和T=V-S两部分，使得s∈S，t∈T。如果f是一个流，则穿过割(S,T)的净流被定义为f(S,T)=∑f(x,y)(x∈S,y∈T)，割(S,T)的容量为c(S,T)。[5]一个网络的最小割就是网络中所有割中具有最小容量的割。设f为G中的一个流，且(S,T)是G中的一个割，则通过割(S,T)的净流f(S,T)=|f|。因为f(S,T)=f(S,V)-f(S,S)=f(S,V)=f(s,V)+f(S-s,V)=f(s,V)=|f|（这里的公式根据f(X,Y)=∑f(x,y)(x∈X,y∈Y)的定义，以及前面的三个限制应该还是可以推出来的，这里就不细讲了）。有了上面这个定理，我们可以知道当把流不断增大时，流f的值|f|不断的接近最小割的容量直到相等，如果这时可以再增大流f，则f必定会超过某个最小的割得容量，则就会存在一个f(S,T)<=c(S,T)<|f|，显然根据上面的定理这是不可能。所以最大流必定不超过网络最小割的容量。综合上面所讲，有一个很重要的定理：最大流最小割定理如果f是具有源s和汇点t的流网络G=(V,E)中的一个流，则下列条件是等价的：1)f是G中一个最大流。2)残留网络Gf不包含增广路径。3)对G的某个割(S,T)，有|f|=c(S,T)。第二章最小费用流问题1最小费用流问题时间压力指的是由时间限制所引发的压力感以及因为必须在时间限制内完成决策所产生的运用有限时间的需求。人们常常倾向于能够在设定的时间之前尽早完成任务，在很多方面可以体现为时间压力下所作不同的决策。对施工方来说，提前竣工可以加快资金运作，节省间接费用。在满足约束条件的情况下，通过合理的安排施工作业时序和资源配置可以得到满意的工期。从工程施工案例可以看出，在时间压力下施工方需要改变施工工序、手段或方式来缩短工期，同样对于不法公职人员来讲，一旦被举报，尤其是在有案底的情况下，时间较短的洗钱路径往往成为其转移不法所得的首要路径选择．为了迅速转移非法资产，一些不法公职人员往往不惜花费巨额手续费，将钱通过地下钱庄、对外贸易等方式转移出去。最小费用最大流问题是经济学和管理学中的一类典型问题。在一个网络中每段路径都有“容量”和“费用”两个限制的条件下，此类问题的研究试图寻找出：流量从A到B，如何选择路径、分配经过路径的流量，可以在流量最大的前提下，达到所用的费用最小的要求。[7]如n辆卡车要运送物品，从A地到B地。由于每条路段都有不同的路费要缴纳，每条路能容纳的车的数量有限制，最小费用最大流问题指如何分配卡车的出发路径可以达到费用最低，物品又能全部送到。2最小费用流问题的模型建立解决最小费用最大流问题，一般有两条途径。一条途径是先用最大流算法算出最大流，然后根据边费用，检查是否有可能在流量平衡的前提下通过调整边流量，使总费用得以减少？只要有这个可能，就进行这样的调整。调整后，得到一个新的最大流。[8]然后，在这个新流的基础上继续检查，调整。这样迭代下去，直至无调整可能，便得到最小费用最大流。这一思路的特点是保持问题的可行性（始终保持最大流），向最优推进。另一条解决途径和前面介绍的最大流算法思路相类似，一般首先给出零流作为初始流。[9]这个流的费用为零，当然是最小费用的。然后寻找一条源点至汇点的增流链，但要求这条增流链必须是所有增流链中费用最小的一条。如果能找出增流链，则在增流链上增流，得出新流。将这个流做为初始流看待，继续寻找增流链增流。这样迭代下去，直至找不出增流链，这时的流即为最小费用最大流。这一算法思路的特点是保持解的最优性（每次得到的新流都是费用最小的流），而逐渐向可行解靠近（直至最大流时才是一个可行解）。由于第二种算法和已介绍的最大流算法接近，且算法中寻找最小费用增流链，可以转化为一个寻求源点至汇点的最短路径问题，所以这里介绍这一算法。在这一算法中，为了寻求最小费用的增流链，对每一当前流，需建立伴随这一网络流的增流网络。例如图1网络G是具有最小费用的流，边旁参数为c(e),f(e),w(e），而图2即为该网络流的增流网络G′。增流网络的顶点和原网络相同。按以下原则建立增流网络的边：若G中边（u，v）流量未饱，即f(u,v)<e(u,v），则G'中建边（u,v），赋权w'(u,v)=w(u,v）；若G中边（u,v）已有流量，即f(u,v）〉0，则G′中建边（v,u），赋权w′（v,u)=-w(u,v）。建立增流网络后，即可在此网络上求源点至汇点的最短路径，以此决定增流路径，然后在原网络上循此路径增流。这里，运用的仍然是最大流算法的增流原理，唯必须选定最小费用的增流链增流。[10]计算中有一个问题需要解决。这就是增流网络G′中有负权边，因而不能直接应用标号法来寻找x至y的最短路径，采用其它计算有负权边的网络最短路径的方法来寻找x至y的最短路径，将大大降低计算效率。为了仍然采用标号法计算最短路径，在每次建立增流网络求得最短路径后，可将网络G的权w(e）做一次修正，使再建的增流网络不会出现负权边，并保证最短路径不至于因此而改变。下面介绍这种修改方法。当流值为零，第一次建增流网络求最短路径时，因无负权边，当然可以采用标号法进行计算。[11]为了使以后建立增流网络时不出现负权边，采取的办法是将G中有流边（f(e)>0）的权w(e）修正为0。为此，每次在增流网络上求得最短路径后，以下式计算G中新的边权w"(u,v）：w"(u,v)=L(u)-L(v)+w(u,v)(*)式中L(u),L(v)--计算G′的x至y最短路径时u和v的标号值。第一次求最短径时如果（u,v）是增流路径上的边，则据最短路径算法一定有L(v)=L(u)+w'(u,v)=L(u)+w(u,v），代入（*）式必有w″（u,v)=0。如果（u,v）不是增流路径上的边，则一定有：L(v）≤L(u)+w(u,v），代入（*）式则有w”(u,v）≥0。可见第一次修正w(e）后，对任一边，皆有w(e）≥0，且有流的边（增流链上的边），一定有w(e)=0。以后每次迭代计算，若f(u,v)>0，增流网络需建立（v,u）边，边权数w'(v,u)=-w(u,v)=0，即不会再出现负权边。此外，每次迭代计算用（*）式修正一切w(e），不难证明对每一条x至y的路径而言，其路径长度都同样增加L(x)-L(y）。因此，x至y的最短路径不会因对w(e）的修正而发生变化。【计算步骤】⒈对网络G=[V,E,C,W]，给出流值为零的初始流。⒉作伴随这个流的增流网络G′=[V′，E′，W′]。G′的顶点同G：V′=V。若G中f(u,v)<c(u,v），则G′中建边（u,v），w(u,v)=w(u,v）。若G中f(u,v)>0，则G′中建边（v,u），w′（v,u)=-w(u,v）。⒊若G′不存在x至y的路径，则G的流即为最小费用最大流，停止计算；否则用标号法找出x至y的最短路径P。⒋根据P，在G上增流：对P的每条边（u,v），若G存在（u,v），则（u,v）增流；若G存在（v,u），则（v,u）减流。增（减）流后，应保证对任一边有c(e）≥f(e）≥0。⒌根据计算最短路径时的各顶点的标号值L(v），按下式修改G一切边的权数w(e):L(u)-L(v)+w(e）→w(e）。⒍将新流视为初始流，转2。3最小费用最大流介绍3.1最小费用最大流的模型

在保证流量最大的前提下，所需的费用最小，这就是最小费用最大流问题．

线性规划的一类重要应用是网络最优化问题或称网络规划,网络流在生产和社会实践中有着广泛的应用,是组合优化及图论中被广泛研究的问题领域之一,横跨多个学科的研究,包括应用数学、计算机科学、工程学、管理学以及运筹学等等。最小费用流是最为基本的网络流模型,它是指在一个给定的网络中求一个从发点到收点的流值为某一给定常数的流,使其费用最小。最小费用流问题是一个常用的组合优化问题,对于该模型已有丰富的研究成果,在理论和实践中都有着广泛的应用,许多实际的网络流问题如运输问题、最短路问题、最大流问题、指派问题等问题都可以转化为最小费用流问题求解。但是随着人类活动和生产过程的日益复杂,新问题不断出现,这对原有的网络模型构成了挑战,也为网络流的进一步发展提供了良好的机遇。有时一些数据并不是很精确的,有可能进行修改,也有可能增加或减少新的变量或新的约束条比如有时需要对一些边进行调整,以满足决策的要求,一些边的特性进行调整后,整个网络规划的最小费用流可能发生变化,因而就有可能涉及整个规划方案的修改,对于一些大型的交互式图上作业就不合适,我们希望在一个尽可能小的范围内,利用原有信息进行适当修正。这些调整是否对原网络最优方案有影响,如果产生影响,变化后的最优方案又是什么,对这些问题的研究被称为灵敏度分析。本文利用最小费用流的网络特性,对其一方面做了灵敏度分析。带有费用的网络流图：G=（V，E，C，W）

V：顶点；E：弧；C：弧的容量；W：单位流量费用。

任意的弧<i,j>对应非负的容量c[i，j]和单位流量费用w[i，j]。满足：

①流量f是G的最大流。

②在f是G的最大流的前提下，流的费用最小。

F是G的最大流的集合（最大流不止一个）：在最大流中寻找一个费用最小的流f．

3.2最小费用最大流的算法

基本思路：

把弧<i,j>的单位费用w[i,j]看作弧<i,j>的路径长度，每次找从源点s到汇点t长度最短（费用最小）的可增广路径进行增广。

1.最小费用可增广路

2.路径s到t的长度即单位流量的费用。第三章：路径规划1路径规划介绍路径规划是指，在具有障碍物的环境中，按照一定的评价标准，寻找一条从起始状态到目标状态的无碰撞路径。本算法中路径规划采用了基于知识的遗传算法，它包含了自然选择和进化的思想，具有很强鲁棒性。2路径规划算法图由节点和带有方向的边构成，每条边都有相应的权值，路径规划（最短路径）算法就是要找出从节点A到节点B的累积权值最小的路径。

首先，我们可以将“有向边”抽象为Edge类：节点则抽象成Node类，一个节点上挂着以此节点作为起点的“出边”表。

在计算的过程中，我们需要记录到达每一个节点权值最小的路径，这个抽象可以用PassedPath类来表示：

另外，还需要一个表PlanCourse来记录规划的中间结果，即它管理了每一个节点的PassedPath。

在所有的基础构建好后，路径规划算法就很容易实施了，该算法主要步骤如下：

(1)用一张表(PlanCourse)记录源点到任何其它一节点的最小权值，初始化这张表时，如果源点能直通某节点，则权值设为对应的边的权，否则设为double.MaxValue。

(2)选取没有被处理并且当前累积权值最小的节点TargetNode，用其边的可达性来更新到达其它节点的路径和权值（如果其它节点

经此节点后权值变小则更新，否则不更新），然后标记TargetNode为已处理。[12]

(3)重复(2)，直至所有的可达节点都被处理一遍。

(4)从PlanCourse表中获取目的点的PassedPath，即为结果。

详解：

(1)用一张表(PlanCourse)记录源点到任何其它一节点的最小权值，初始化这张表时，如果源点能直通某节点，则权值设为对应的

边的权，否则设为double.MaxValue

(2)选取没有被处理并且当前累积权值最小的节点TargetNode，用其边的可达性来更新到达其它节点的路径和权值（如果其它节点

经此节点后权值变小则更新，否则不更新），然后标记TargetNode为已处理

(3)重复(2)，直至所有的可达节点都被处理一遍。

(4)从PlanCourse表中获取目的点的PassedPath，即为结果。第四章最小费用最大流算法在路径规划中的应用1最短路算法1.1问题引入问题：从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径——最短路径。解决最短路的问题有以下算法，Dijkstra算法，Bellman-Ford算法，Floyd算法和SPFA算法，另外还有著名的启发式搜索算法A*，不过A*准备单独出一篇，其中Floyd算法可以求解任意两点间的最短路径的长度。笔者认为任意一个最短路算法都是基于这样一个事实：从任意节点A到任意节点B的最短路径不外乎2种可能，1是直接从A到B，2是从A经过若干个节点到B。[13]1.2.Dijkstra算法该算法在《数据结构》课本里是以贪心的形式讲解的，不过在《运筹学》教材里被编排在动态规划章节，建议读者两篇都看看。观察右边表格发现除最后一个节点外其他均已经求出最短路径。

(1)

迪杰斯特拉(Dijkstra)算法按路径长度(看下面表格的最后一行，就是next点)递增次序产生最短路径。先把V分成两组：S：已求出最短路径的顶点的集合V-S=T：尚未确定最短路径的顶点集合将T中顶点按最短路径递增的次序加入到S中，依据：可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的直接路径的权值或是从V0经S中顶点到Vk的路径权值之和（反证法可证，说实话，真不明白哦）。

(2)求最短路径步骤初使时令S={V0},T={其余顶点}，T中顶点对应的距离值，

若存在<V0,Vi>，为<V0,Vi>弧上的权值（和ＳＰＦＡ初始化方式不同），若不存在<V0,Vi>，为Inf。从T中选取一个其距离值为最小的顶点W(贪心体现在此处)，加入S(注意不是直接从S集合中选取，理解这个对于理解vis数组的作用至关重要)，对T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值（上面两个并列for循环，使用最小点更新）。重复上述步骤，直到S中包含所有顶点，即S=V为止（说明最外层是除起点外的遍历）。[14]下面是上图的求解过程，按列来看，第一列是初始化过程，最后一行是每次求得的next点。

(3)

问题：Dijkstar能否处理负权边？

答案是不能，这与贪心选择性质有关，每次都找一个距源点最近的点（dmin），然后将该距离定为这个点到源点的最短路径；但如果存在负权边，那就有可能先通过并不是距源点最近的一个次优点（dmin'），再通过这个负权边L(L<0)，使得路径之和更小（dmin'+L<dmin）,则dmin'+L成为最短路径，并不是dmin，这样dijkstra就被囧掉了。比如n=3，邻接矩阵：

0，3，4

3，0，-2

4，-2，0,用dijkstra求得d[1，2]=3，事实上d[1，2]=2，就是通过了1-3-2使得路径减小。不知道讲得清楚不清楚。[15]1.3.Floyd算法Floyd算法的基本思想如下：从任意节点A到任意节点B的最短路径不外乎2种可能，1是直接从A到B，2是从A经过若干个节点到B，所以，我们假设dist(AB)为节点A到节点B的最短路径的距离，对于每一个节点K，我们检查dist(AK)+dist(KB)<dist(AB)是否成立，如果成立，证明从A到K再到B的路径比A直接到B的路径短，我们便设置dist(AB)=dist(AK)+dist(KB)，这样一来，当我们遍历完所有节点K，dist(AB)中记录的便是A到B的最短路径的距离。[16]

但是这里我们要注意循环的嵌套顺序，如果把检查所有节点K放在最内层，那么结果将是不正确的，为什么呢？因为这样便过早的把i到j的最短路径确定下来了，而当后面存在更短的路径时，已经不再会更新了。让我们来看一个例子，如下图：图中红色的数字代表边的权重。如果我们在最内层检查所有节点K，那么对于A->B，我们只能发现一条路径，就是A->B，路径距离为9，而这显然是不正确的，真实的最短路径是A->D->C->B，路径距离为6。造成错误的原因就是我们把检查所有节点K放在最内层，造成过早的把A到B的最短路径确定下来了，当确定A->B的最短路径时dist(AC)尚未被计算。所以，我们需要改写循环顺序，如下：

for(intk=0;k<n;++k){for(inti=0;i<n;++i){for(intj=0;j<n;++j){/*实际中为防止溢出，往往需要选判断dist[i][k]和dist[k][j都不是Inf，只要一个是Inf，那么就肯定不必更新。*/if(dist[i][k]+dist[k][j]<dist[i][j]){dist[i][j]=dist[i][k]+dist[k][j];}}}}

再来看路径保存问题：voidfloyd(){for(inti=1;i<=n;i++){for(intj=1;j<=n;j++){if(map[i][j]==Inf){path[i][j]=-1;//表示i->j不通}else{path[i][j]=i;//表示i->j前驱为i}}}for(intk=1;k<=n;k++){for(inti=1;i<=n;i++){for(intj=1;j<=n;j++){if(!(dist[i][k]==Inf||dist[k][j]==Inf)&&dist[i][j]>dist[i][k]+dist[k][j]){dist[i][j]=dist[i][k]+dist[k][j];path[i][k]=i;path[i][j]=path[k][j];}}}}}voidprintPath(intfrom,intto){/**这是倒序输出，若想正序可放入栈中，然后输出。**这样的输出为什么正确呢？个人认为用到了最优子结构性质，*即最短路径的子路径仍然是最短路径*/while(path[from][to]!=from){System.out.print(path[from][to]+"");to=path[from][to];}}Floyd算法另一种理解DP，为理论爱好者准备的，上面这个形式的算法其实是Floyd算法的精简版，而真正的Floyd算法是一种基于DP(DynamicProgramming)的最短路径算法。设图G中n个顶点的编号为1到n。令c[i,j,k]表示从i到j的最短路径的长度，其中k表示该路径中的最大顶点，也就是说c[i,j,k]这条最短路径所通过的中间顶点最大不超过k。因此，如果G中包含边<i,j>，则c[i,j,0]=边<i,j>的长度；若i=j，则c[i,j,0]=0；如果G中不包含边<i,j>，则c(i,j,0)=+∞。c[i,j,n]则是从i到j的最短路径的长度。对于任意的k>0，通过分析可以得到：中间顶点不超过k的i到j的最短路径有两种可能：该路径含或不含中间顶点k。若不含，则该路径长度应为c[i,j,k-1]，否则长度为c[i,k,k-1]+c[k,j,k-1]。c[i,j,k]可取两者中的最小值。状态转移方程：c[i,j,k]=min{c[i,j,k-1],c[i,k,k-1]+c[k,j,k-1]}，k＞0。这样，问题便具有了最优子结构性质，可以用动态规划方法来求解。

以ZOJ1092为例：给你一组国家和国家间的部分货币汇率兑换表，问你是否存在一种方式，从一种货币出发，经过一系列的货币兑换，最后返回该货币时大于出发时的数值(ps：这就是所谓的投机倒把吧)，下面是一组输入。

3

//国家数

USDollar

//国家名

BritishPound

FrenchFranc

3

//货币兑换数

USDollar0.5BritishPound

//部分货币汇率兑换表

BritishPound10.0FrenchFranc

FrenchFranc0.21USDollar思路分析：输入的时候可以采用Map<String,Integer>map=newHashMap<String,Integer>()主要是为了获得再次包含汇率输入时候的下标以建图，或者第一次直接存入String数组str，再次输入的时候每次遍历str数组，若是equals那么就把str的下标赋值给该币种建图。下面就是floyd算法啦，初始化其它点为-1，对角线为1，采用乘法更新求最大值。1.4.Bellman-Ford算法为了能够求解边上带有负值的单源最短路径问题，Bellman(贝尔曼，动态规划提出者)和Ford(福特)提出了从源点逐次绕过其他顶点，以缩短到达终点的最短路径长度的方法。

Bellman-ford算法是求含负权图的单源最短路径算法，效率很低，但代码很容易写。即进行不停地松弛，每次松弛把每条边都更新一下，若n-1次松弛后还能更新，则说明图中有负环，无法得出结果，否则就成功完成。Bellman-ford算法有一个小优化：每次松弛先设一个flag，初值为FALSE，若有边更新则赋值为TRUE，最终如果还是FALSE则直接成功退出。Bellman-ford算法浪费了许多时间做无必要的松弛，所以SPFA算法用队列进行了优化，效果十分显著，高效难以想象。SPFA还有SLF，LLL，滚动数组等优化。关于SPFA，/hxsyl/p/3248391.html递推公式(求顶点u到源点v的最短路径)：dist1[u]=Edge[v][u]distk[u]=min{distk-1[u],min{distk-1[j]+Edge[j][u]}},j=0,1,…,n-1,j≠u

Dijkstra算法和Bellman算法思想有很大的区别：Dijkstra算法在求解过程中，源点到集合S内各顶点的最短路径一旦求出，则之后不变了，修改

的仅仅是源点到T集合中各顶点的最短路径长度。Bellman算法在求解过程中，每次循环都要修改所有顶点的dist[]，也就是说源点到各顶点最短路径长度一直要到Bellman算法结束才确定下来。

算法适用条件1.单源最短路径(从源点s到其它所有顶点v)有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图)边权可正可负(如有负权回路输出错误提示)差分约束系统(至今貌似只看过一道题)

Bellman-Ford算法描述：初始化：将除源点外的所有顶点的最短距离估计值d[v]←+∞,d[s]←0迭代求解：反复对边集E中的每条边进行松弛操作，使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离；（运行|v|-1次，看下面的描述性证明(当做树)）1.检验负权回路：判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点，则算法返回false，表明问题无解；否则算法返回true，并且从源点可达的顶点v的最短距离保存在d[v]中描述性证明：首先指出，图的任意一条最短路径既不能包含负权回路，也不会包含正权回路，因此它最多包含|v|-1条边。其次，从源点s可达的所有顶点如果存在最短路径，则这些最短路径构成一个以s为根的最短路径树。Bellman-Ford算法的迭代松弛操作，实际上就是按顶点距离s的层次，逐层生成这棵最短路径树的过程。在对每条边进行1遍松弛的时候，生成了从s出发，层次至多为1的那些树枝。也就是说，找到了与s至多有1条边相联的那些顶点的最短路径；对每条边进行第2遍松弛的时候，生成了第2层次的树枝，就是说找到了经过2条边相连的那些顶点的最短路径……。因为最短路径最多只包含|v|-1条边，所以，只需要循环|v|-1次。每实施一次松弛操作，最短路径树上就会有一层顶点达到其最短距离，此后这层顶点的最短距离值就会一直保持不变，不再受后续松弛操作的影响。（但是，每次还要判断松弛，这里浪费了大量的时间，这就是Bellman-Ford算法效率底下的原因，也正是SPFA优化的所在）。如图(没找到画图工具的射线)，若是B和C的最短路径不更新，那么点D的最短路径肯定也无法更新，这就是优化所在。如果没有负权回路，由于最短路径树的高度最多只能是|v|-1，所以最多经过|v|-1遍松弛操作后，所有从s可达的顶点必将求出最短距离。如果d[v]仍保持+∞，则表明从s到v不可达。如果有负权回路，那么第|v|-1遍松弛操作仍然会成功，这时，负权回路上的顶点不会收敛。问题：Bellman-Ford算法是否一定要循环n-1次么？未必！其实只要在某次循环过程中，考虑每条边后，都没能改变当前源点到所有顶点的最短路径长度，那么Bellman-Ford算法就可以提前结束了(开篇提出的小优化就是这个)。#include<iostream>#include<cstdio>usingnamespacestd;#defineMAX0x3f3f3f3f#defineN1010intnodenum,edgenum,original;//点，边，起点typedefstructEdge//边{intu,v;intcost;}Edge;Edgeedge[N];intdis[N],pre[N];boolBellman_Ford(){for(inti=1;i<=nodenum;++i)//初始化dis[i]=(i==original?0:MAX);for(inti=1;i<=nodenum-1;++i)for(intj=1;j<=edgenum;++j)if(dis[edge[j].v]>dis[edge[j].u]+edge[j].cost)//松弛（顺序一定不能反~）{dis[edge[j].v]=dis[edge[j].u]+edge[j].cost;pre[edge[j].v]=edge[j].u;}boolflag=1;//判断是否含有负权回路for(inti=1;i<=edgenum;++i)if(dis[edge[i].v]>dis[edge[i].u]+edge[i].cost){flag=0;break;}returnflag;}voidprint_path(introot)//打印最短路的路径（反向）{while(root!=pre[root])//前驱{printf("%d-->",root);root=pre[root];}if(root==pre[root])printf("%d\n",root);}intmain(){scanf("%d%d%d",&nodenum,&edgenum,&original);pre[original]=original;for(inti=1;i<=edgenum;++i){scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].cost);}if(Bellman_Ford())for(inti=1;i<=nodenum;++i)//每个点最短路{printf("%d\n",dis[i]);printf("Path:");print_path(i);}elseprintf("havenegativecircle\n");return0;}1.5.SPFA算法求单源最短路的SPFA算法的全称是：ShortestPathFasterAlgorithm，是西南交通大学段凡丁于1994年发表的。从名字我们就可以看出，这种算法在效率上一定有过人之处。很多时候，给定的图存在负权边，这时类似Dijkstra算法等便没有了用武之地，而Bellman-Ford算法的复杂度又过高，SPFA算法便派上用场了。简洁起见，我们约定加权有向图G不存在负权回路，即最短路径一定存在。如果某个点进入队列的次数超过N次则存在负环（SPFA无法处理带负环的图）。当然，我们可以在执行该算法前做一次拓扑排序，以判断是否存在负权回路，但这不是我们讨论的重点。我们用数组d记录每个结点的最短路径估计值，而且用邻接表来存储图G。我们采取的方法是动态逼近法：设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。定理：只要最短路径存在，上述SPFA算法必定能求出最小值。证明：每次将点放入队尾，都是经过松弛操作达到的。换言之，每次的优化将会有某个点v的最短路径估计值d[v]变小。所以算法的执行会使d越来越小。由于我们假定图中不存在负权回路，所以每个结点都有最短路径值。因此，算法不会无限执行下去，随着d值的逐渐变小，直到到达最短路径值时，算法结束，这时的最短路径估计值就是对应结点的最短路径值。期望时间复杂度：O(me)，其中m为所有顶点进队的平均次数，可以证明m一般小于等于2：“算法编程后实际运算情况表明m一般没有超过2n.事实上顶点入队次数m是一个不容易事先分析出来的数,但它确是一个随图的不同而略有不同的常数.所谓常数,就是与e无关,与n也无关,仅与边的权值分布有关.一旦图确定,权值确定,原点确定,m就是一个确定的常数.所以SPFA算法复杂度为O(e).证毕."（SPFA的论文）不过，这个证明是非常不严谨甚至错误的，事实上在bellman算法的论文中已有这方面的内容，所以国际上一般不承认SPFA算法。对SPFA的一个很直观的理解就是由无权图的BFS转化而来。在无权图中，BFS首先到达的顶点所经历的路径一定是最短路(也就是经过的最少顶点数)，所以此时利用数组记录节点访问可以使每个顶点只进队一次，但在带权图中，最先到达的顶点所计算出来的路径不一定是最短路。一个解决方法是放弃数组，此时所需时间自然就是指数级的，所以我们不能放弃数组，而是在处理一个已经在队列中且当前所得的路径比原来更好的顶点时，直接更新最优解。SPFA算法有两个优化策略SLF和LLL——SLF：SmallLabelFirst策略，设要加入的节点是j，队首元素为i，若dist(j)<dist(i)，则将j插入队首，否则插入队尾；LLL：LargeLabelLast策略，设队首元素为i，队列中所有dist值的平均值为x，若dist(i)>x则将i插入到队尾，查找下一元素，直到找到某一i使得dist(i)<=x，则将i出队进行松弛操作。SLF可使速度提高15~20%；SLF+LLL可提高约50%。在实际的应用中SPFA的算法时间效率不是很稳定，为了避免最坏情况的出现，通常使用效率更加稳定的Dijkstra算法。2.

配送区域动态优化及其方法2.1配送区域的初始划分方法。配送区域优化方法对最终优化的结果有很大的影响，因而合理的划分方法的选择十分重要，目前常用的划分方法有扫描法和聚类算法，在配送客户有限、区域较小时运用扫描法就可以了，但是当客户数量很多，区域较大，又要考虑约束条件时，聚类算法就是我们必然的选择了，聚类算法中K-means比较成熟，操作简单，原理是：把大量d维(二维)数据对象n个聚集成k个聚类k在运用聚类分析法时有几个问题要注意：第一，k的选择，以一天送货总量/单车载重量，也可以放宽一些，到：一天送货总量/单车载重量+1。第二，k个聚类内的密度，分区密度大，效率高，成本低。第三，每个分区内工作时间大体相当，这样便于运行的稳定，进行成本控制和人员、车辆的考核。第四，每个聚类间不重合。做到这样分区效果会比较好。传统的K-means聚类法，k个聚类区内，初始点是随机产生的，运行时间长，收敛效果差。基于均衡化考虑，在配送对象分布不均匀时，用密度法效果较好，初始中心点以密度来定义，运用两点间欧氏距离方法，求解所有对象间的相互距离，并求平均数，用meanD表示，确定领域半径R，n是对象数目，coefR是半径调节系数，0coefR=0.13时，效果最好。如果使用平均欧氏距离还不理想，可增加距离长度，甚至用最大距离选择法，收敛速度比较快。在配送对象分布较均匀时，可考虑用网格法，效果较好，整个配送区域划分用k=Q/q，k为初始点个数，假设k=mn，将地图划分成m行n列，以每格中心点为初始点，通过网格内的反复聚类运算，达到收敛，获得网格稳定的聚类中心。2.2分区内配送工作量的均衡。这样就完成了配送区域的初步划分，但是没有考虑各个分区内工作量的均衡问题，如果工作量不均衡，对于客户服务水平的保证，成本的控制，作业的安排，人员、车辆的考核都存在问题。在实际的物流企业配送作业过程中，一般一辆车一天也就送货10多家或20来家，多余的时间要用于收款，与公司财务部门交账，核算出车相关费用，所以不考虑同一车同一天出车多次的情况，多次出车待以后深入探讨。那么就意味着每个分区就是一辆车一条线路，把问题大大简化了，需要说明的是：这种方法对于配送规模不是特别大的单个城市配送是适用的，也具有广泛性。各分区内的每日配送工作量是以配送作业耗用时间来衡量的，耗用时间有两部分构成：(1)车辆行驶时间;(2)客户服务时间。由于配送分区有限，每个分区内的客户数量不是很多，可以采用实地测时的方式，把每条线路的配送时间统计出来，这是一种手工办法，但比较符合实际来调整超过差值的分区内的客户，从而使得各区作业时间基本均衡。如果客户数量众多，分区也较复杂，就需要借助统计学方法，通过对样本线路车辆行驶时间以及服务时间，拟合出分区作业时间函数，然后，计算出所有线路作业时间，即使分区重新调整，线路重新组合，仍可以很快计算出线路作业时间。本文不在这个方面进行深入探讨。2.3重新组合客户，确定最终区域划分。观察各线路作业时间超过允许差值的部分，由大到小来调整，将离聚类中心最远的数据点弹出，使本区