沈阳师范大学微课教学方案设计-沈阳师范大学教务处

1、单源最短路径教学方案设计教学内容§7.6.1 从某个源点到课程名称数据结构其余各顶点的最短路径所属专业工学类 计算机科学与技术授课对象计算机科学与技术专业本科生使用教材严蔚敏 . 数据结构（ C语言版）清华大学出版社， 2013教学手段多媒体教学（ PPT课件）教学方式问题导入、案例贯通式交通网络中常常提出这样的问题：两地之间是否有路相通？在有多条通路的情况下，哪一条最短？交通网络可以用带权图表示，图中顶点表示城镇，边表示两个城镇之间的道路，边上权值可以表示两城镇间的距离，交通费用或图中所需的时间等等。以上提出的问题就是带权图中求最短路径的问题，即求两个顶点间长度最短的路径，这里路径

2、长度不是指路径上边数的总和，而是教学背景指路径上各边的权值总和，它的具体含义取决于边上权值所代表的意义。为解决此问题，迪杰斯特拉提出了按路径长度递增序产生从某个源点出发到诸顶点的最短路径算法。该知识点内容具有较强的理论性。学生应该在理解单源最短路径问题的基础上，学习单源最短路径算法的原理，最后掌握求解单源最短路径的方法。因此，该知识点适合采用问题导入的方式，由实际应用案例贯穿原理的讲授与应用的掌握。理解：单源最短路径问题。教学目标掌握： Dijkstra 算法的原理；求解单源最短路径的方法。重点：源点、终点、最短路径概念；教学重点Dijkstra 算法的原理。教学难点难点：根据给定的带权有向图

3、用Dijkstra 算法求解给定源点到各顶点的单源最短路径及路径长度。1.提出问题（ 1 分钟）教学设计什么是路径？2. 导入案例（ 2 分钟）以某交通网络规划为例，提出最短路径、源点、终点的概念，引出解决最短路径方法的思考。3.提出解决方法 Dijkstra算法（ 10 分钟）1 ）单源最短路径概念；2 ） Dijkstra 算法的原理及基本思想；3 ） Dijkstra 算法的基本步骤；4 ）例题。4. 总结（ 2 分钟）5. 课后任务布置（ 1 分钟）1. 导入问题回顾：路径的概念顶点的序列 V=Vi0 ,V i1 , Vin ，满足(Vij-1 ,V ij )E 或 <Vij-1

4、 ,V ij > E,(1<jn) 。提出问题：通过案例提出问题从某顶点出发， 沿图的边到达另一顶点所经过的路径中，如何找到各边上权值之和最小的一条路径最短路径？2. 本节内容关注教学过程源点：路径上的第一个顶点；终点：路径上的最后一个顶点；路径长度：路径上边的权值之和；最短路径：给定带权有向图G，从源点到终点路径长度最短的路径；提出解决最短路径问题的方法：Dijkstra算法。3. 引入本节主要内容1）单源最短路径的定义：给定带权有向图G和源点 v, 求从 v 到 G 中其余各顶点的最短路径。2 ）求解单源最短路径的原理：按路径长度递增序产生诸顶点的最短路径。3 ）Dijkstr

5、a 算法的基本思想及步骤。设置例题，巩固单源最短路径的求解方法。5. 总结本节内容6. 布置课后练习及预习的内容整个教学过程采用问题导入、启发引导的教学方式。运用多媒体教学手段，结合提示、动画演示，将讲授内容直观呈现给学生。先回顾问题，再通过当前最火爆的物流问题提出如何规划路线使得两城市之间的距离或费用最短，引导学生思考。给出解决方法，即图，给出图示。将此图贯穿整个教学环节，引导学生自教学方法己找出源点，终点及自己给出最短路径概念；提出如何求解最短路径的问题，再基于出现的问题，用单源最短路径的方法进行解决，给出单源最短路径的概念， 及 Dijkstra算法的基本思想及步骤，在讲解步骤中用实例对概念进行解释，最后，通过例子解决一个单源最短路径问题。 整个过程循序渐进， 让学生从提出问题，到解决问题，最后可以灵活运用。习题：对下图所示的带权有向图，利用 DIJKSTRA算法求从源点 v0 到其它各顶点的最短路径。v032813习题及作业30v2v1759v6v3176v52v4课后任务：1复习 Dijkstra 算法；2预习 Dijkstra 算法的实现。理解 Dijkstra 算法求解单源最短路径的原理及方法是本节的重点，灵活运用Dijkstra 算法根据实际需求求解最短路径是本节教学总结的难点。通过本节的学习，学生可以对日常路径规划问题更为熟练