数学建模迪杰斯特拉算法例题ppt课件.pptVIP

数学建模专题练习 迪杰斯特拉算法2014 09 1 例一 用Dijkstra算法求下图从v1到v6的最短路 解 1 首先给v1以P标号 给其余所有点T标号 2 2 4 3 5 6 反向追踪得v1到v6的最短路为 4 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 例二 求从1到8的最短路径 5 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X 1 min d12 d14 d16 min 0 2 0 1 0 3 min 2 1 3 1X 1 4 p4 1 p4 1 p1 0 6 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X 1 4 min d12 d16 d42 d47 min 0 2 0 3 1 10 1 2 min 2 3 11 3 2X 1 2 4 p2 2 p1 0 p4 1 p2 2 7 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X 1 2 4 min d16 d23 d25 d47 min 0 3 2 6 2 5 1 2 min 3 8 7 3 3X 1 2 4 6 p6 3 p2 2 p4 1 p1 0 p6 3 8 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X 1 2 4 6 min d23 d25 c47 d67 min 2 6 2 5 1 2 3 4 min 8 7 3 7 3X 1 2 4 6 7 p7 3 p2 2 p4 1 p1 0 p6 3 p7 3 9 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X 1 2 4 6 7 min d23 d25 d75 d78 min 2 6 2 5 3 3 3 8 min 8 7 6 11 6X 1 2 4 5 6 7 p5 6 p2 2 p4 1 p1 0 p6 3 p7 3 p5 6 10 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X 1 2 4 6 7 min d23 d53 d58 d78 min 2 6 6 9 6 4 3 8 min 8 15 10 11 8X 1 2 3 4 5 6 7 p3 8 p2 2 p4 1 p1 0 p6 3 p7 3 p5 6 p3 8 11 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X 1 2 3 4 6 7 min d38 d58 d78 min 8 6 6 4 3 7 min 14 10 11 10X 1 2 3 4 5 6 7 8 p8 10 p2 2 p4 1 p1 0 p6 3 p7 3 p5 6 p3 8 p8 10 12 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 X 1 2 3 4 6 7 8 1到8的最短路径为 1 4 7 5 8 长度为10 p2 2 p4 1 p1 0 p6 3 p7 3 p5 6 p3 8 p8 10 13 例三 下图为单行线交通网 每弧旁的数字表示通过这条线所需的费用 现在某人要从v1出发 通过这个交通网到v8去 求使总费用最小的旅行路线 14 从v1到v8 P1 v1 v2 v5 v8 费用6 1 6 13P2 v1 v3 v4 v6 v7 v8 费用3 2 10 2 4 21P3 最短路问题中 不考虑有向环 并行弧 15 最短路问题 给定有向网络D V A W 任意弧aij A 有权w aij wij 给定D中的两个顶点vs vt 设P是D中从vs到vt的一条路 定义路P的权 长度 是P中所有弧的权之和 记为w P 最短路问题就是要在所有从vs到vt的路中 求一条路P0 使 称P0是从vs到vt的最短路 路P0的权称为从vs到vt的路长 记为ust 16 当所有wij 0时 本算法是用来求给定点vs到任一个点vj最短路的公认的最好方法 事实 如果P是D中从vs到vj的最短路 vi是P中的一个点 那么 从vs沿P到vi的路是从vs到vi的最短路 最短路的子路也是最短路 17 思想 将D V A W 中vs到所有其它顶点的最短路按其路长从小到大排列为 u0 u1 u2 un u0表示vs到自身的长度 相应最短路记为 P0 P1 P2 Pn 取最小值的点为v1 P1 P vs v1 假定u0 u1 uk的值已求出 对应的最短路分别为 P1 P vs v1 P2 P vs v2 Pk P vs vk P1一定只有一条弧 18 记 则 使上式达到最小值的点v 可取为vk 1 计算过程中可采用标号方法 Xk中的点 ui值是vs到vi的最短路长度 相应的点记 永久 标号 前点标号 i 表示点vs到vj的最短路上vj的前一点 如 i m 表示vs到vj的最短路上vj前一点是vm 19 1 6 图上标号法 0 0 1 1 1 1 1 1 1 1 3 20 1 6 图上标号法 0 0 1 1 1 1 1 1 1 1 3 21 1 6 0 0 1 4 11 1 1 1 1 1 1 3 图上标号法 22 1 5 0 0 1 4 11 1 1 1 1 1 1 3 1 6 图上标号法 23 1 5 0 0 1 4 11 1 1 1 1 1 1 3 3 5 图上标号法 24 3 5 0 0 1 4 11 1 1 1 1 1 3 1 图上标号法 25 3 5 0 0 1 4 11 1 1 1 1 1 3 1 图上标号法 26 3 5 0 0 4 11 1 1 1 2 6 1 1 3 1 图上标号法 27 3 5 0 0 4 11 1 1 1 2 6 1 1 3 1 图上标号法 28 3 5 0 0 5 10 1 1 1 2 6 5 12 1 3 5 9 图上标号法 29 3 5 0 0 5 10 1 1 1 2 6 5 12 1 3 5 9 图上标号法 30 Dijkstra算法步骤 第1步 令us 0 uj wsj 1 j n 若asj A 则 第3步 给点vi永久性标号 第4步 修改临时标号 对所有如果 令 j i uj ui wij否则 i uj不变 把k换成k 1 返回第2步 如果ui 停止 31 例三 用Dijkstra算法求前面例子中从v1到各点的最短路 解 u1 0 u2 6 u3 3 u4 1 u5 u6 u7 u8 u9 j 1 j 2 3 9 X0 v1 X0 v2 v3 v9 32 K 0 min u2 u3 u4 u5 u6 u7 u8 u9 min 6 3 1 1 u4 u6 u4 w46 1 10 11 即u4 w46 u6 修改临时标号u6 11 6 4 其余标号不变 33 K 0 1 1 min u2 u3 u5 u6 u7 u8 u9 min 6 3 11 3 u3 u2 6 u3 w32 3 2 5 即u3 w32 u2 修改临时标号u2 5 2 3 其余标号不变 34 k 2 1 3 min u5 u6 u7 u8 u9 min 6 11 6 u5 u6 11 u5 w56 6 4 10 即u5 w56 u6u7 u5 w57 6 3 9 即u5 w57 u7u8 u5 w58 6 6 12 即u5 w58 u8 修改临时标号u6 10 6 5 u7 9 7 5 u8 12 8 5 35 K 3 1 4 min u6 u7 u8 u9 min 10 9 12 9 u7 K 4 1 5 min u6 u8 u9 min 10 12 10 u6 点v8 v9临时标号不变 36 K 5 1 6 min u8 u9 min 12 12 u8 点v8得永久标号 8 5 即从v1到v8的最短路长为u8 12 8 5 5 2 2 3 3 1 知从v1到v8的最短路为 P1 8 P v1 v3 v2 v5 v8 37 例四 如图所示 令S a b f 则S c d e 求d a S 38 Dijkstra算法 设u0 a 取u a 则w ac w ad 10 w ae 39 取u b 则d a b 6 w bc 5 w bd w be 4 取u f 则d a f 1 w fc 1 w fd w fe 2 因而d a S 2 a到S 的最短路为 a f c Dijkstra算法 40 Dijkstra算法 指导思想 设u0 V v0 V 要求u0到v0点的距离 我们通过求u0到图中其它各点的距离 先把V分成两个子集 一个设为S S v v V u0到v的距离已求出 另一个是S V S 显然 S 因为至少u0 S 算法不断扩大S 直到S V 或者v0 S 对任意的v S V u0 设l v 表示从u0仅经过S中的点到v的