授课教案
Dijkstra算法是由E.W.Dijkstra于1959年提出，又叫迪杰斯特拉算法，它应用了贪心算法模式，是目前公认的最好的求解最短路径的方法。算法解决的是有向图中单个源点到其他顶点的最短路径问题，其主要特点是每次迭代时选择的下一个顶点是标记点之外距离源点最近的顶点。但由于Dijkstra算法主要计算从源点到其他所有点的最短路径，所以算法的效率较低。
3、Dijkstra算法描述：
Dijkstra算法的流程图
4、实例讲解：
接下来我们将通过一个实例对Dijkstra算法有一个进一步的深层体会。
如下图，设1为源点，求1到其他各顶点（2，3，4，5，6）的最短路径。线上所标注为相邻线段之间的距离，即权值。
例图
Dijkstra算法矩阵图
依次找出最短路径，然后将涉及到的结点加入进已用结点的集合中，再次计算最短路径，确定最终的最短路径
通过对整个过程的讲述,同学们可以掌握Dijkstra算法的逻辑思路及相关的一些计算。
第三步（2分钟）讨论与提问
让同学们从计算讲解过程中，发现Dijkstra算法的的优缺点。
第四步（1分钟）总结与布置作业
（1）优点：算法简明、能得到最优解
（2）缺点：效率低（特别是有时候不需要最优解）、运算中占用空间大
（3）Dijkstra算法是应用贪心算法设计的一个典型例子。
（4）Dijkstra算法适用于权值为非负的图的单源最短路径，用斐波那契堆的复杂度O(E+VlgV)