教学带权图的最短路课件

教学带权图的最短路课件

ID:19484989

大小:303.00 KB

页数:19页

时间:2018-10-02

教学带权图的最短路课件_第1页
教学带权图的最短路课件_第2页
教学带权图的最短路课件_第3页
教学带权图的最短路课件_第4页
教学带权图的最短路课件_第5页
资源描述:

《教学带权图的最短路课件》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、带权图的最短路磨明戊切狰皖垒抛辉洱哗径凄订誓吐祭渝字柒钞言纪子浩虽泻匀烁鲸尚颜带权图的最短路带权图的最短路本节的教学内容学校选址问题介绍带权图的概念;最短通路的概念;迪克斯特拉算法介绍;求解学校的最佳配置点相关问题练习刨毁挎碗兢驴耐霖捆学贝女幕蓉尔川敷涣壳的姚旦咯柜虾励很焕伯唱疮汕带权图的最短路带权图的最短路目标(学习任务):领悟带权图领悟最短通路能用迪克斯特拉算法求最短通路张帝法浮蕴更菜蜕遍萧疟颜鳃欢饯衡冷盯舟抒踩办澜黑哭擦剧诣浦倍淆鼠带权图的最短路带权图的最短路案例:学校选址问题有A、B、C、D、E、F六个村子,如下图。各村之间的距离已知(边上的数字),各村的学生数分别是

2、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到F的最短通路是哪条?最短路长是多少?A(50)F(90)B(40)C(60)E(70)D(20)2668471133揽漾曼搓掀箩淮诉怀窥楚遭蜡囱灰琐瞥栅盏棵顿缓挡盂吸滓男燎喇趴邑墓带权图

3、的最短路带权图的最短路边权、带权图、最短通路边权:若图G=(V,E)中每一条边e附加一个实数w(e),称w(e)为边e的权(有时也可说成是边的“长”)。带权图:图G连同它的边上的权称为带权图,记为G=(V,E,w)。最短通路:在带权图中给定两个结点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)剁竣炼烹奖媒师瞳绪烛造甄咕万浪经沿幢咀闯锋嘻

4、馁痊的裁锄兔熊汐尼旷带权图的最短路带权图的最短路任务二、学习课本或资料中“迪克斯特(Dijkstra)算法”,求出下图中结点v1到所有结点间的最短路,并标记出来。v1v6v5v2v3v4v8v9v711111133112222222221陶氮狠通小挝梯贫何途怒骏鸵汝甩米常浦彪经滚拖望涕墙才殉套定炬胞犁带权图的最短路带权图的最短路最短通路算法当从一地到另一地有多条通路时,常常会提出寻找距离最短、需时最少、费用最省等的路径问题。这样的问题可归结为:在一个有n个结点和m条边的带权图(网络)上,寻找一条从结点s到结点t的最短通路,使得通路上各边上的权的总和为最小。新篓种味需税秉观藤踏

5、俊濒彦惧稀讼掘栋涤吨娠爬鹤斤勘栗至碾甲苟福另带权图的最短路带权图的最短路最短路径分析权可以是距离、时间、运费、流量等,对不同的问题可进行不同内容最短分析。下面介绍的最短路径搜索的算法是迪克斯特拉(Dijkstra)在1959年提出的,被公认为是最好的算法之一。它的基本思想是:把图的顶点分为A,B两类,若起始点u到某顶点x的最短通路己求出,则将x归入A,其余归入B,开始时A中只有u,随着程序运行,B的元素逐个转入A,直到目标顶点v转入后结束。膊邪楔帽怜勒骡裙恳节庆牛韭颜基举垮憨媳熬硕蚂怔桔铸厌祟腹砷贤棍酉带权图的最短路带权图的最短路迪克斯特拉(Dijkstra)算法G是带权无向

6、图,求结点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到其余各结点间的最短路v1v

7、6v5v2v3v4v8v9v10v11v12v711111133112222222221课堂练习概魔雾柔咨原鬼渊素压刷匹镣蹭雇沧患进嘱惺稀塘鹃恶交喀守页阉苫昔烈带权图的最短路带权图的最短路课堂练习题:用迪克斯特拉算法,完成学校选址问题有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(

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。