运筹学-路径问题(名校讲义).pptVIP

第二十六、二十七讲 路径问题 §1 两点间的最短路问题 §2 最小生成树问题 §3 邮路问题及旅行推销员问题 §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 §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的长度 §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) §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。 §1 两点间的最短路问题 （5） 例如，试求图5-14中v1至vj（j=2，?，7）的最短路径。步骤如下： 1）首先给v1一个永久性标号0，则v1?A中，其它顶点标出试探性标号为+?，参见表5-4。（本节所列表中的k表示阶段）。 表5-4 l(v) v k v1 v2 v3 v4 v5 v6 v7 1 0* +? +? +? +? +? +? §1 两点间的最短路问题 （6） 2) 利用v1得到永久性标号，计算 中各点新试探标号。 l(v2)=min{ l(v1)+W12，l(v2)}=min{0+5，+?}=5 l(v3)=min{ l(v1)+W13，l(v3)}=min{0+4，+?}=4 同理得：l(v4)=7，l(v5)= +?，l(v6)= +?，l(v7)= +?。 取标号最小者为l(v3)=4，于是d(v3)=4，v3?A，见表5-5。 表5-5 l(v) v k v2 v3 v4 v5 v6 v7 2 5 4* 7 +? +? +? §1 两点间的最短路问题 （7） 3) v*= v3，用它计算 中各点新试探标号。 l(v2)=min{ l(v3)+W32，l(v2)}=min{4+?，5}=5 同理，l(v4)=6，l(v5)=12，l(v6)= +?，l(v7)= +?，继续迭代可得表5-6。 最后得出：d(v1)=0，d(v2)=5，d(v3)=4，d(v4)=6，d(v5)=9，d(v6)=8，d(v7)=13 当求v1至t点的最短路径时，可从t点向前递推（见教材[例5-15]。 §1 两点间的最短路问题 （8） 表5-6 l(v) v k v1 v2 v3 v4 v5 v6 v7 1 0* +? +? +? +? +? +? 2 5 4* 7 +? +? +? 3 5* 6 12 +? +? 4 6* 10 8 +? 5 10 8* +? 6 9* 14 7 13* §1 两点间的最短路问题 （9） 寻找最优路径的第二种方法是，把结果表与网络图结合起来，找出哪些永久标号值之差恰等于连接边的权的顶点，然后这些顶点之间连线即为最短路径。