（73）带权图的最短路课件

带权图的最短路,本节的教学内容,学校选址问题介绍 带权图的概念； 最短通路的概念； 迪克斯特拉算法介绍； 求解学校的最佳配置点 相关问题练习,本节课的要求,应知：带权图、最短通路的概念 应会：用迪克斯特拉算法求最短通路,学校选址问题,有A、B、C、D、E、F六个村子，如下图。各村之间的距离已知（边上的数字），各村的学生数分别是A：50人，B：40人，C：60人，D：20人，E：70人，F：90人。现要在公路旁的D村或E村建一所学校，问校址选在何处，才能使所有学生所走的总路程最短？,边权、带权图、最短通路,边权：若图G（V,E）中每一条边e附加一个实数w(e),称w(e)为边e的权(有时也可说成是边的“长”)。 带权图：图G连同它的边上的权称为带权图，记为G=(V,E,w)。 最短通路：在带权图中给定两个结点vi与vj，如果从vi到vj有多条通路，构成某通路的边的“长”的和叫做该通路的“长度；从vi到vj的所有通路中，“长度”最小的通路叫做从vi到vj的最短通路。,如图右中，点D到F的最短通路是“DEF”(长度4),最短通路算法,当从一地到另一地有多条通路时，常常会提出寻找距离最短、需时最少、费用最省等的路径问题。这样的问题可归结为：在一个有a个结点和b条边的带权图（网络）上，寻找一条从结点s到结点t的最短通路，使得通路上各边上的权的总和为最小。,最短路径分析,权可以是距离、时间、运费、流量等，对不同的问题可进行不同内容最短分析。下面介绍的最短路径搜索的算法是迪克斯特拉（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中。,（4）重复(2)、(3)两步，直到终点出现在A中为止。,上述过程可以直接用一个表格完成：,1 2 3 4 5 6,从此例我们可以看到该表格有以下特点： 从任何一个结点列来看，都是单调不增； 从距离列来看，是单调不减；其值等于该行的最小数字 最短路径为该最小数字首次出现前的最短路径该结点,a,0,12,10,5,4,3,a,f,d,a,f,e,c,a,f,e,a,f,b,a,f,12,12,12,10,11,4 *,6,5,5,3*,0,*,*,12,*,*,Example 如图，求出该图中结点v1到其余各结点间的最短路。,1、如图，求出该图中结点v7到其余各结点间的最短路。,课堂练习,校址选在何处（D为起点）,A,F,B,C,E,D,2,6,6,8,4,7,1,1,3,3,第二步,A,F,B,C,E,D,2,6,6,8,4,7,1,1,3,3,第三步,A,F,B,C,E,D,2,6,6,8,4,7,1,1,3,3,第四步,A,F,B,C,E,D,2,6,6,8,4,7,1,1,3,3,第一步,校址选在何处（E为起点）,A,F,B,C,E,D,2,6,6,8,4,7,1,1,3,3,第二步,7,A,F,B,C,E,D,2,6,6,8,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,所有学生步行上学的总长度: 7505401601704901040,A到E:ABCDE8 B到E:BCDE6 C到E:CDE 2 D到E:DE 1 F到E:FE 3,若选在E,所有学生步行上学的总长度: 8506402601203901050,A (50),F (90),B(40),C(60),E(70),D(20),2,6,6,8,4,7,1,1,3,3,图 32-1,选D,校址选在E处学生步行总长度,实训练习,求下列带权网络中从结点v1到结点v9的最短通路，边上的数字是该边上的权。,练习答案,求下列赋权网络中从结点v1到结点v9的最短通路(边上