资源描述：
《带权图的最短路.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
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)2668471133任务一:学习
2、课本,请完成下列任务什么图是带权图，举例；在下图中点D到F的最短通路是哪条？最短路长是多少？A(50)F(90)B(40)C(60)E(70)D(20)2668471133边权、带权图、最短通路边权：若图G＝（V,E）中每一条边e附加一个实数w(e),称w(e)为边e的权(有时也可说成是边的“长”)。带权图：图G连同它的边上的权称为带权图，记为G=(V,E,w)。最短通路：在带权图中给定两个结点vi与vj，如果从vi到vj有多条通路，构成某通路的边的“长”的和叫做该通路的“长度；从vi到vj的所有通路中，“长度”最小的通路叫做从vi到vj的最短通路
3、。A(50)F(90)B(40)C(60)E(70)D(20)2668471133如图右中，点D到F的最短通路是“DEF”(长度＝4)任务二、学习课本或资料中“迪克斯特(Dijkstra)算法”，求出下图中结点v1到所有结点间的最短路，并标记出来。v1v6v5v2v3v4v8v9v711111133112222222221最短通路算法当从一地到另一地有多条通路时，常常会提出寻找距离最短、需时最少、费用最省等的路径问题。这样的问题可归结为：在一个有n个结点和m条边的带权图（网络）上，寻找一条从结点s到结点t的最短通路，使得通路上各边上的权的总和为最小
4、。最短路径分析权可以是距离、时间、运费、流量等，对不同的问题可进行不同内容最短分析。下面介绍的最短路径搜索的算法是迪克斯特拉（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中某些结点邻接的那
5、些结点进行考察，找出与起点a距离最短的一个结点v（若存在多个，任选一个），记录这条最短路的长度，记做d(v)。（3）将找出的结点v从B中划到A中。并且在A中增加点a与点v间所有边；在B中减去与点v间的所有边。（4）重复(2)、(3)两步，直到终点出现在A中为止。所有结点v考察的是哪些点?记录的是哪个点?如图，求出该图中结点v7到其余各结点间的最短路v1v6v5v2v3v4v8v9v10v11v12v711111133112222222221课堂练习课堂练习题:用迪克斯特拉算法，完成学校选址问题有A、B、C、D、E、F六个村子，如下图。各村之间的距离
6、已知（边上的数字），各村的学生数分别是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)2668471133校址选在何处（D为起点）AFBCED2668471133第二步AFBCED2668471133第三步AFBCED2668471133第四步AFBCED2668471133第一步校址选在何处（E为起点）AFBCED2668471133第一步AFBCED2668471133第二步[7
7、]AFBCED2668471133第三步FBDACE2668471133第四步校址选在D处学生步行总长度如此下去可得：A到D:ABCD→7B到D:BCD→5C到D:CD→1E到D:ED→1F到D:FED→4若选在D,所有学生步行上学的总长度:7×50＋5×40＋1×60＋1×70＋4×90＝1040A(50)F(90)B(40)C(60)E(70)D(20)2668471133图32-1A到E:ABCDE→8B到E:BCDE→6C到E:CDE→2D到E:DE→1F到E:FE→3若选在E,所有学生步行上学的总长度:8×50＋6×40＋2×60＋1×2
8、0＋3×90＝1050A(50)F(90)B(40)C(60)E(70)D(20)2668471133图32-1∴选D校址
