数据结构 单源最短路径教学设计

《单源最短路径》教学方案设计
教学内容
§7.6.1从某个源点到其余各顶点的最短路径
课程名称
《数据结构》
所属专业
工学类 计算机科学与技术
授课对象
计算机科学与技术专业本科生
使用教材
严蔚敏. 数据结构（C语言版）清华大学出版社，2013
教学手段
多媒体教学（PPT课件）
教学方式
问题导入、案例贯通式
教学背景
交通网络中常常提出这样的问题：两地之间是否有路相通？在有多条通路的情况下，哪一条最短？交通网络可以用带权图表示，图中顶点表示城镇，边表示两个城镇之间的道路，边上权值可以表示两城镇间的距离，交通费用或图中所需的时间等等。以上提出的问题就是带权图中求最短路径的问题，即求两个顶点间长度最短的路径，这里路径长度不是指路径上边数的总和，而是指路径上各边的权值总和，它的具体含义取决于边上权值所代表的意义。为解决此问题，迪杰斯特拉提出了按路径长度递增序产生从某个源点出发到诸顶点的最短路径算法。
该知识点内容具有较强的理论性。学生应该在理解单源最短路径问题的基础上，学习单源最短路径算法的原理，最后掌握求解单源最短路径的方法。因此，该知识点适合采用问题导入的方式，由实际应用案例贯穿原理的讲授与应用的掌握。
教学目标
理解：单源最短路径问题。
掌握：Dijkstra算法的原理；
求解单源最短路径的方法。
教学重点
教学难点
重点：源点、终点、最短路径概念；
Dijkstra算法的原理。
难点：根据给定的带权有向图用Dijkstra算法求解给定源点到各顶点的单源最短路径及路径长度。
教学设计
1. 提出问题（1分钟）
什么是路径？
2. 导入案例（2分钟）
以某交通网络规划为例，提出最短路径、源点、终点的概念，引出解决最短路径方法的思考。
3. 提出解决方法—Dijkstra算法（10分钟）
1）单源最短路径概念；
2）Dijkstra算法的原理及基本思想；
3）Dijkstra算法的基本步骤；
4）例题。
4. 总结（2分钟）
5. 课后任务布置（1分钟）
教学过程
1. 导入问题
回顾：路径的概念
——顶点的序列V={Vi0,Vi1,……Vin}，满足
(Vij-1,Vij)ÎE 或 <Vij-1,Vij>ÎE,(1<j£n)。
提出问题：通过案例提出问题
——从某顶点出发，沿图的边到达另一顶点所
经过的路径中，如何找到各边上权值之和最小的一条路径——最短路径？
2. 本节内容关注
源点：路径上的第一个顶点；
终点：路径上的最后一个顶点；
路径长度：路径上边的权值之和；
最短路径：给定带权有向图G，从源点到终点路径
长度最短的路径；
提出解决最短路径问题的方法：Dijkstra算法。
3. 引入本节主要内容
1）单源最短路径的定义：给定带权有向图G和源点v,求从v到G中其余各顶点的最短路径。
2）求解单源最短路径的原理：按路径长度递增序产生
诸顶点的最短路径。
3）Dijkstra算法的基本思想及步骤。
设置例题，巩固单源最短路径的求解方法。
5. 总结本节内容
6. 布置课后练习及预习的内容
教学方法
整个教学过程采用问题导入、启发引导的教学方式。运用多媒体教学手段，结合提示、动画演示，将讲授内容直观呈现给学生。
先回顾问题，再通过当前最火爆的物流问题提出如何规划路线使得两城市之间的距离或费用最短，引导学生思考。给出解决方法，即图，给出图示。将此图贯穿整个教学环节，引导学生自己找出源点，终点及自己给出最短路径概念；提出如何求解最短路径的问题，再基于出现的问题，用单源最短路径的方法进行解决，给出单源最短路径的概念，及Dijkstra算法的基本思想及步骤，在讲解步骤中用实例对概念进行解释，最后，通过例子解决一个单源最短路径问题。整个过程循序渐进，让学生从提出问题，到解决问题，最后可以灵活运用。
习题及作业
习题：
对下图所示的带权有向图，利用DIJKSTRA算法求从源点v0到其它各顶点的最短路径。
课后任务：
1．复习Dijkstra算法；
2．预习Dijkstra算法的实现。
教学总结
理解Dijkstra算法求解单源最短路径的原理及方法是本节的重点，灵活运用Dijkstra算法根据实际需求求解最短路径是本节的难点。
通过本节的学习，学生可以对日常路径规划问题更为熟练，并能够掌握解决单源最短路径问题的方法。
参考教材
1．《数据结构—用C语言描述》，唐策善，高等教育出版社，2004.3；
2．《新编数据结构习题与解析》，李春葆，清华大学出版社，2013.5。

› 数据结构期末试卷

› 数据结构 单源最短路径教学设计