带权图的最短路课件

本节的教学内容本节的教学内容学校选址问题介绍学校选址问题介绍带权图的概念；带权图的概念；最短通路的概念；最短通路的概念；迪克斯特拉算法介绍；迪克斯特拉算法介绍；求解学校的最佳配置点求解学校的最佳配置点相关问题练习相关问题练习 本节的教学内容学校选址问题介绍 目标（学习任务）：目标（学习任务）：领悟带权图领悟最短通路能用迪克斯特拉算法求最短通路 目标（学习任务）：领悟带权图案例：案例：学校选址问题学校选址问题 有有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案例：学校选址问题 有A、B、C、D、E、F六个村子任务一任务一:学习课本学习课本,请完成下列任务请完成下列任务1.什么图是带权图，举例；什么图是带权图，举例；2.在下图中在下图中点点D到到F的最短通路是哪条？的最短通路是哪条？最短路长是多少？最短路长是多少？A(50)F(90)B(40)C(60)E(70)D(20)2668471133任务一:学习课本,请完成下列任务什么图是带权图，举 边权、带权图、最短通路边权、带权图、最短通路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)2668471133如图右中，点如图右中，点D到到F的最短通路是的最短通路是“DEF”(长度长度4)边权、带权图、最短通路边权：若图G（V,E）中每一条边e任务二、学习课本或资料中任务二、学习课本或资料中“迪克斯特迪克斯特(Dijkstra)算法算法”，求出下图中结点求出下图中结点v v1到所有到所有结点间的最短路，并标记出来。结点间的最短路，并标记出来。v1v6v5v2v3v4v8v9v711111133112222222221任务二、学习课本或资料中“迪克斯特(Dijkstra)算法”最短通路算法最短通路算法 当从一地到另一地有多条通路时，常常会提出当从一地到另一地有多条通路时，常常会提出寻找距离最短、需时最少、费用最省等的路径问题。寻找距离最短、需时最少、费用最省等的路径问题。这样的问题可归结为：在一个有这样的问题可归结为：在一个有n n个结点和个结点和m m条边的条边的带权图（网络）上，寻找一条从结点带权图（网络）上，寻找一条从结点s s到结点到结点t t的最的最短通路，使得通路上各边上的权的总和为最小。短通路，使得通路上各边上的权的总和为最小。最短通路算法 当从一地到另一地有多条通路时，常常会提出 最短路径分析最短路径分析 n权可以是距离、时间、运费、流量等，对不同的问题可权可以是距离、时间、运费、流量等，对不同的问题可进行不同内容最短分析。下面介绍的最短路径搜索的算进行不同内容最短分析。下面介绍的最短路径搜索的算法是法是迪克斯特拉（迪克斯特拉（DijkstraDijkstra）在在19591959年提出的，被公认年提出的，被公认为是最好的算法之一。它的基本思想是为是最好的算法之一。它的基本思想是:把图的顶点分把图的顶点分为为A,BA,B两类两类,若起始点若起始点u u到某顶点到某顶点x x的最短通路己求出的最短通路己求出,则则将将x x归入归入A,A,其余归入其余归入B,B,开始时开始时A A中只有中只有u,u,随着程序运行随着程序运行,B,B的元素逐个转入的元素逐个转入A,A,直到目标顶点直到目标顶点v v转入后结束转入后结束。最短路径分析 权可以是距离、时间、运费、流量等，对不同的迪克斯特拉(Dijkstra)算法G G 是带权无向图是带权无向图，求求结点结点a a 到到G G 的的任意结点任意结点v v 的最短路。的最短路。（1）令）令A A=a a,B B 包括图包括图G G中去掉结点中去掉结点a a的所有剩余部分。的所有剩余部分。（2）对）对B B 中直接和中直接和A A中中某些结点邻接的那些结点进行某些结点邻接的那些结点进行考考 察察，找出与起点，找出与起点a a 距离最短的一个结点距离最短的一个结点v v（若存在多个，（若存在多个，任选一个），任选一个），记录记录这条最短路的长度，记做这条最短路的长度，记做d d(v v)。（3）将找出的结点）将找出的结点v v从从B B中划到中划到A A中。并且在中。并且在A A中增加点中增加点a a与点与点v v间所有边；在间所有边；在B B中减去与点中减去与点v v间间的所有边。的所有边。（4）重复）重复(2)、(3)两步，直到终点出现在两步，直到终点出现在A中为止。中为止。所有结点所有结点v考察的是哪些点考察的是哪些点?记录的是哪个点记录的是哪个点?迪克斯特拉(Dijkstra)算法G 是带权无向图，求结点如图，求出该图中结点如图，求出该图中结点v v7到其余各结点间的最短路到其余各结点间的最短路v1v6v5v2v3v4v8v9v10v11v12v711111133112222222221课堂练习课堂练习如图，求出该图中结点v7到其余各结点间的最短路v1v6v5v课堂练习题课堂练习题:用迪克斯特拉算法用迪克斯特拉算法，完成学，完成学 校选址问题校选址问题 有有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课堂练习题:用迪克斯特拉算法，完成学 校选址问题 校址选在何处（校址选在何处（D D为起点）为起点）A FBCED2668471133第二步A FBCED2668471133第三步A FBCED2668471133第四步A FBCED2668471133第一步校址选在何处（D为起点）A FBCED2668471133第 校址选在何处（校址选在何处（E E为起点）为起点）A FBCED2668471133第一步A FBCED2668471133第二步7A FBCED2668471133第三步 FBDACE2668471133第四步 校址选在何处（E为起点）A FBCED2668471133校址选在校址选在D D处处学生步行总长度学生步行总长度如此下去可得：如此下去可得：A到到D:ABCD7B到到D:BCD5C到到D:CD 1E到到D:ED 1F到到D:FED 4若选在若选在D,所有学生步行上学的总长度所有学生步行上学的总长度:7505401601704901040 A(50)F(90)B(40)C(60)E(70)D(20)2668471133图 32-1校址选在D处学生步行总长度如此下去可得：若选在D,所有学生步A到到E:ABCDE8B到到E:BCDE6C到到E:CDE 2D到到E:DE 1F到到E:FE 3若选在若选在E,所有学生步行上学的总长度所有学生步行上学的总长度:8506402601203901050 A(50)F(90)B(40)C(60)E(70)D(20)2668471133图 32-1选选D校址选在校址选在E E处处学生步行总长度学生步行总长度A到E:ABCDE8若选在E,所有学生步行上学的总长度:u 课堂练习课堂练习求下列带权网络中从结点求下列带权网络中从结点v1到结点到结点v9的最短通路，的最短通路，边上的数字是该边上的权。边上的数字是该边上的权。v2v5v1v3v4v6v7v9v833332222244444 课堂练习求下列带权网络中从结点v1到结点v9的最短通路，边u 练习答案练习答案求下列赋权网络中从结点v1到结点v9的最短通路(边上的数字是该边上的权)，并求最短通路的长度。v2v5v1v3v4v6v7v9v833332222244444答案：答案：P=v1v2v5v9 LP=10 练习答案求下列赋权网络中从结点v1到结点v9的最短通路(边