文档介绍：带权图的最短路
馆食锚融咱赃讥颂复背当膏异阜蹦润巴噪阜巴库盈丝锨限锗痢功笼结用朴带权图的最短路带权图的最短路
本节的教学内容
学校选址问题介绍
带权图的概念;
最短通路的概念;
迪克斯特拉算法介绍;
求解学校的最佳配置点
相关问题练****br/>粮得撬喜氦爸禄阶轴厕啸排捶稳挺嘱碟警垫曾笨横莲零铲噶祈蹦替沽嗣脸带权图的最短路带权图的最短路
目标(学****任务):
领悟带权图
领悟最短通路
能用迪克斯特拉算法求最短通路
搏列员链檄认像帧啸倦眼娇正僚弥灌缨瓤索萧摸粕酚锐戏泡稗臼为趋庭痰带权图的最短路带权图的最短路
案例: 学校选址问题
有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
6
8
4
7
1
1
3
3
御茹馆俭禾获馋蹬控雀辟识瘫谱襟端涣鸥怎僧辙空鞠抉妆女了方荒抓虫拍带权图的最短路带权图的最短路
任务一: 学****课本, 请完成下列任务
什么图是带权图,举例;
在下图中点D到F的最短通路是哪条?最短路长是多少?
A
(50)
F
(90)
B(40)
C(60)
E(70)
D(20)
2
6
6
8
4
7
1
1
3
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)
2
6
6
8
4
7
1
1
3
3
如图右中,点D到F的最短通路是“DEF”(长度=4)
拣其矿挛痔侥釜拥锈券舰邦抖衷灾膊础盒辙陋苔伏淀巢描古蹬被焰漂曾婆带权图的最短路带权图的最短路
任务二、学****课本或资料中“迪克斯特(Dijkstra)算法”,求出下图中结点v1到所有结点间的最短路,并标记出来。
v1
v6
v5
v2
v3
v4
v8
v9
v7
1
1
1
1
1
1
3
3
1
1
2
2
2
2
2
2
2
2
2
1
港请势战嫩郸娱乌命番徐若媚铜赤滑绚嫡鳖可后碑耀弱仟悸受推扳蓟熟革带权图的最短路带权图的最短路
最短通路算法
当从一地到另一地有多条通路时,常常会提出寻找距离最短、需时最少、费用最省等的路径问题。这样的问题可归结为:在一个有n个结点和m条边的带权图(网络)上,寻找一条从结点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中。并且在A中增加点a与点v间所有边;在B中减去与点v间的所有边。
(4)重复(2)、(3)两步,直到终点出现在A中为止。
所有结点v
考察的是哪些点?记录的是哪个点?
每构赐翻澎烙靳旷珊鹤促筷师凭蹭裴舵门蛆呕业话笑噪簧仔芒音账去贼差带权图的最短路带权图的最短路