带权图的最短路.ppt

带权图的最短路 本节的教学内容 学校选址问题介绍 带权图的概念； 最短通路的概念； 迪克斯特拉算法介绍； 求解学校的最佳配置点 相关问题练习 目标（学习任务） ： 领悟带权图 领悟最短通路 能用迪克斯特拉算法求最短通路 案例： 学校选址问题 有A、B、C、D、E、F六个村子，如下图。各村之间的距离已 知（边上的数字），各村的学生数分别是A：50人，B：40人 ，C：60人，D：20人，E：70人，F：90人。现要在公路旁 的D村或E村建一所学校，问校址选在何处，才能使所有学生所 走的总路程最短？ A (50) F (90) B(40 ) C(60)E(70) D(20 ) 2 6 68 4 7 1 1 3 3 任务一: 学习课本, 请完成下列任务 1.什么图是带权图，举例； 2.在下图中点D到F的最短通路是哪条？ 最短路长是多少？ A (50 ) F (90 ) B(40 ) C(60 ) E(70 ) D(20 ) 2 6 68 4 7 1 1 3 3 边权、带权图、最短通路 n边权：若图G（V,E）中每一条边e附加一个实数w(e),称w(e) 为边e的权(有时也可说成是边的“长”)。 n带权图：图G连同它的边上的权称为带权图，记为G=(V,E,w)。 n最短通路：在带权图中给定两个结点vi与vj，如果从vi到vj有多条 通路，构成某通路的边的“长”的和叫做该通路的“长度；从vi到vj的 所有通路中，“长度”最小的通路叫做从vi到vj的最短通路。 A (50 ) F (90 ) B(40 ) C(60 ) E(70 ) D(20 ) 2 6 68 4 7 1 1 3 3 如图右中，点D到F 的最短通路是 “DEF”(长度4) 任务二、学习课本或资料中“迪克斯特 (Dijkstra)算法”，求出下图中结点v1到所有 结点间的最短路，并标记出来。 v1 v6 v5 v2v3v4 v8 v9 v7 1 11 1 1 1 3 3 1 1 2 2 2 2 2 22 2 2 1 最短通路算法 当从一地到另一地有多条通路时，常常会提出寻 找距离最短、需时最少、费用最省等的路径问题。 这样的问题可归结为：在一个有n个结点和m条边 的带权图（网络）上，寻找一条从结点s到结点t的 最短通路，使得通路上各边上的权的总和为最小。 最短路径分析 n权可以是距离、时间、运费、流量等，对不同的问题可 进行不同内容最短分析。下面介绍的最短路径搜索的算 法是迪克斯特拉（Dijkstra）在1959年提出的，被公认为 是最好的算法之一。它的基本思想是:把图的顶点分为 A,B两类,若起始点u到某顶点x的最短通路己求出,则将x 归入A,其余归入B,开始时A中只有u,随着程序运行,B的元 素逐个转入A, 直到目标顶点v转入后结束。 迪克斯特拉(Dijkstra)算法 G 是带权无向图 ，求结点a 到G 的任意结点v 的最短路 。 （1）令A =a,B 包括图G中去掉结点a的所有剩余部分。 （2）对B 中直接和A中某些结点邻接的那些结点进行考 察，找出与起点a 距离最短的一个结点v（若存在多个， 任选一个），记录这条最短路的长度，记做d (v)。 （3）将找出的结点v从B中划到A中。并且在A中增加点a 与点v间所有边；在B中减去与点v间的所有边。 （4）重复(2)、(3)两步，直到终点出现在A中为止。 所有结点v 考察的是哪些点?记录的是哪个点? 如图，求出该图中结点v7到其余各结点间的最短路 v1 v6 v5 v2v3v4 v8 v9v1 0 v1 1 v1 2 v7 1 11 1 1 1 3 3 1 1 2 2 2 2 2 22 2 2 1 课堂练习 课堂练习题: 用迪克斯特拉算法 ，完成学 校选址问题 有A、B、C、D、E、F六个村子，如下图。各村之间的距离 已知（边上的数字），各村的学生数分别是A：50人，B：40人 ，C：60人，D：20人，E：70人，F：90人。现要在公路旁的D 村或E村建一所学校，问校址选在何处，才能使所有学生所走的 总路程最短？ A (50) F (90) B(40 ) C(60)E(70) D(20 ) 2 6 68 4 7 1 1 3 3 校址选在何处（D为起点 ） A F B CE D 2 6 68 4 7 1 1 33 第二步 A F B CE D 2 6 68 4 7 1 1 33 第三步 A F B CE D 2 6 68 4 7 1 1 33 第四步 A F B CE D 2 6 68 4 7 1 1 3 3 第一步 校址选在何处（E为起点 ） A F B CE D 2 6 68 4 7 1 1 3 3 第一步 A F B CE D 2 6 68 4 7 1 1 3 3 第二步 7 A F B CE D 2 6 68 4 7 1 1 3 3 第三步 F BD A CE 2 6 68 4 7 1 1 3 3 第四步 校址选在D处学生步行总长度 如此下去可得： A到D:ABCD7 B到D:BCD5 C到D:CD 1 E到D:ED 1 F到D:FED 4 若选在D,所有学生步行上学的总长度: 750540160170 4901040 A (50) F (90) B(40 ) C(60 ) E(70) D(20 ) 2 6 68 4 7 1 1 3 3 图 32-1 A到E:ABCDE8 B到E:BCDE6 C到E:CDE 2 D到E:DE 1 F到E:FE 3 若选在E,所有学生步行上学的总长度: 850640260120 3901050 A (50) F (90) B(40 ) C(60 ) E(70) D(20 ) 2 6 68 4 7 1 1 33 图 32-1 选D 校址选在E处学生步行总长度 u 课堂练习 求下列带权网络中从结点v1到结点v9的最短通路， 边上的数字是该边上的权。 v2v5 v1v3 v4 v6 v7 v9 v8 3 3 3 3 2 2 2 2 2 4 4 4 4 4 u 练习答案 求下列赋权网络中从结点v1到结