运筹学-路径问题[名校讲义].pptVIP

第二十六、二十七讲 路径问题 §1 两点间的最短路问题 §2 最小生成树问题 §3 邮路问题及旅行推销员问题 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. §1 两点间的最短路问题 （1） [例5-4]已知某区的交通运输的公路分布、走向及相应费用示于有向图5-14中。 ? ? 试问：卡车从v1出发经哪条路线到达v7，才能使总行程最短？这就是网络路径问题的典型提法。 v7 ? ? ? ? ? 0 ? ? v6 v5 v2 v4 v3 v1 7 6 4 1 8 2 4 7 6 5 3 5 5 6 4 9 13 8 5 图5-14 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. §1 两点间的最短路问题 （2） 1．求从某点到其它点的最短路算法 目前大多采用标号法，即E．W．Dijkstra(狄克斯特拉)算法，现就介绍这种算法的思路和具体步骤。 ①有关术语 设在有向图G=（V，E）中，V={v1，v2，?，vn}，E={e1，e2，?，em}，G中每条边e=[ vi，vj]都有一个非负实数权值W(e)，则称G为非负赋权图（权可以表示距离、费用和时间等）。 设P为图G中u至v的路径，则定义： ?W(P) = 为P的长度 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. §1 两点间的最短路问题 （3） ?若P*为G中u至v的路径且满足： W(P)=min[W(P)?P为G中u至v的路径] 则称P*为u至v的最短路径。 ②算法思路： 设起点为v1，希求出从v1到其它顶点最短路，令d(vj)为v1至vj的最短路长度。则 (1) (2) Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. §1 两点间的最短路问题 （4） 对于（2），显然有d(vj)= d(v)+[ v至vj的最短路] 所以d(v)? d(vj)，故在求d(vj)之前，应先求出d(v)。 例如，在图5-14中，已求出v1至其它各点的最短距离示如方框内（求解过程将在后面讲述），由此看出： d(v1) d(v3) d(v2) d(v4) d(v6) d(v5) d(v7)， 则求解次序必为v1? v3??? v7。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. §1 两点间的最短路问题 （5） 例如，试求图5-14中v1至vj（j=2，?，7）的最短路径。步骤如下： 1）首先给v1一个永久性标号0，则v1?A中，其它顶点标出试探性标号为+?，参见表5-4。（本节所列表中的k表示阶段）。 表5-4 l(v) v k 1 v1 0* v2 +? v3 +? v4 +? v5 +? v6 +? v7 +? Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. §1 两点间的最短路问题 （6） 2) 利用v1得到永久性标号，计算 中各点新试探标号。 l(v2)=min{