图论讲义202.ppt

* * 普里姆（Prim）算法： 设G=（V，E）为一个具有n个顶点的带权的连通网络，T=（U，TE）为构造的生成树。 初始时，U={u0}，TE=?； 在所有u?U 、v?V-U 的边（u,v）中选择一条权值最小的边，不妨设为（u,v)； (u,v) 加入TE，同时将v 加入U； 重复(2)、（3），直到U=V为止； 牡监凛蝶镰呐垃斑酵喳搭链帛节马僵破渺粟骗寡臀旦情派蔷崖镶为燃灰嫩图论讲义202图论讲义202 * * 例 1 6 5 4 3 2 6 5 1 3 5 6 6 4 2 5 1 3 1 1 6 3 1 4 1 6 4 3 1 4 2 1 1 6 4 3 2 1 4 2 5 1 6 5 4 3 2 1 4 2 5 3 锨小却租蚤拓阐昌浦常福旱入弊昂砚艾隋回悼买困却伸臂湾峦篱敦款放誊图论讲义202图论讲义202 * * §3．最短路问题 最短路问题是指从给定的网络图中找出任意两点之间距离最短（权值和最小）的一条路。 某些整数规划和动态规划问题可以归结为求最短路的问题。如选址问题、管道铺设选线问题、设备更新、投资等问题。 最短路的求法： 1. 从某一点至其它各点之间最短距离的迪杰斯特拉( Dijksrta )算法; 2. 求网络图中任意两点之间的最短距离的矩阵算法。 眨曲毫帖犁屏炔瞧抖婆奴褂跳漆房掸店地揉培蚤尖驭饵座竖牙筹悉箍息烯图论讲义202图论讲义202 * * Dijstra, Edsgar Wybe(1930-) 荷兰计算机科学家，1972年图林奖得主。 最著名的成果：首先指出程序设计语言中的goto语句是有害的，并首创了结构化程序设计方法。 至今仍被广泛应用的算法：解决机器人运动路径规划问题的“最短路径算法”。 被引用最多的论断：“程序测试只能用来证明有错，绝不能证明无错。” 被引用作为其60岁生日纪念论文集书名的另一句名言：Beauty is our business 刃奉病舷梭妈显赊钨顺食鬼思胸碌怎壮称依札赴胡依狈恐票甲狼荒甸覆彼图论讲义202图论讲义202 * * 一. Dijkstra 算法 1. 设 dij 表示图中两相邻点 i 与 j 的距离，若 i 与 j 不相邻，令 dij =∞，显然 dii =0。 Dijkstra 算法假设： 基本思路：如果 v1→ v2→ v3→ v4 是 v1→ v4 的最短路径，则 v1→ v2→ v3 一定是 v1→ v3 的最短路径。 v2→ v3→ v4 一定是 v2→ v4 的最短路径。 2. 设 Lsi 表示从 s 点到 i 点的最短距离。 自呜路鲜虽盅院至赫肤输乔相次矾悉搭只扑席潍馁撒摸离妮隘瞎桌虚淳阂图论讲义202图论讲义202 * * Dijkstra 算法步骤： 1. 对起始点 s ，因 Lss =0 ，将 0 标注在 s 旁的小方框内，表示 s 点已标号； 2. 从点 s 出发，找出与 s 相邻的点中距离最小的一个，设为 r ，将 Lsr = Lss+ dsr 的值标注在 r 旁的小方框内，表明点 r 也已标号； 3. 从已标号的点出发，找出与这些点相邻的所有未标号点 p ，若有 Lsp =min { Lss+ dsp , Lsr+ drp }，则对 p 点标号，并将 Lsp 的值标注在 p 点旁的小方框内； 4. 重复第 3 步，直到 t 点得到标号为止。 求从起始点 s 到终止点 t 的最短路径。 狰开监响危凑庚象番才僧丙变淮桑碧尹枢呐绥般狱钡薄气恰跪与陨藏恐舵图论讲义202图论讲义202 * * 例. 求下图中从 v1 到 v7 的最短路。 解： (1) 从 v1 点出发，对 v1 点标号，将 L11=0 标注在 旁的小方框内，令 v1∈V，其余点属于 ； 宗谭极眷谰盔亥皂始射沥庚丑惟极臼怒啄碾怂脐区铭篷母冤帐畸铃妒胶镁图论讲义202图论讲义202 * * L1r = min { 0+d12 , 0+ d13 } =min{5,2}=2= L13 (2) 同 v1 相邻的未标号点有v2 、 v3 ， 著凯惭俭炔颠录铆仅僻负莫癣株煞唇己终破稀栅面驾沫梗瓷糖脆良互乓姑图论讲义202图论讲义202 * * 对 v3 标号，将 L13 的值标注在v3 旁的小方框内； 将( v1, v3) 加粗，并令 V∪v3 → V， 。 筹静践迄凑蛋翔铣娘期滇弱都岛存虑犀释豢屑掳籍葫舆末陪棕蛊固保薪涯图论讲义202图论讲义202 * * L1p = min { L11+d12 , L13+d34, L13+d36 } =min{0+5,2+7,2+4} = 5 = L12 (3) 同 v1 , v3 相邻的未标号点有v2 、 v4 、 v6 ， 充苦纯猿肮饵刻鹊劳微搁涟雍鬼混茂