高职班Dijkstra算法的教学体会

许智勇

摘要： 数学是一门抽象性、逻辑性很强的课程，数学教学一直就是一个难题，高职院校的数学教师对此更是颇有同感。教学中作者感觉求解最短路问题的Dijkstra算法难教难学，初学者往往觉得算法的思路很简单，但动起手来却不容易计算正确。如果将算法的计算过程用表格表示，认真思考每一个数据的来历，对算法的理解和掌握将会事半功倍。

关键词： 高职院校Dijkstra算法标号法表格

Dijkstra算法是典型的最短路算法，用于计算一个顶点到其他所有顶点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的顶点很多，因此效率低。但Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构、图论、运筹学等。

给定一个带权有向图，其中每条边的权是一个非负实数。另外给定图中的一个顶点，称为源。现在我们要计算从源到所有其他各顶点的最短路径长度。这里的长度指路上各边权之和。这个问题通常称为单源最短路径问题。Dijkstra算法（标号法）是按各顶点与源点间的路径长度的递增次序，生成源点到各顶点的最短路径的算法，即先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从源点到其他各顶点的最短路径全部求出为止。

关于最短路问题Dijkstra算法的教学，看上去不难，但老师讲授起来很费劲，学生学起来更加感觉困难。对此，不寻找恰当的教学方法，一味地啃书本是难以达到良好的教学效果的。往往还会致使学生厌学，从而对相关课程的学习失去兴趣。高职学生相对于其他普通本科院校的学生，在数学学习方面能力要弱一些，因此，高職院校的数学教师更应该注意寻找适合的教学方法来提高学生的学习兴趣，从而提高课堂教学效率。教师应改变过去“填鸭式”、“灌输式”的教学方法，充分发挥学生的主体作用，灵活运用启发式教学方法，激发学生思维和质疑，培养学生的创新精神和独立探讨问题的能力。要引导学生对问题多思考，多问几个“为什么”，抓住内容相关和相反的部分，对知识进行横向和纵向的比较，并掌握它们之间的内在联系和规律，培养学生系统而全面的思维方式。教师应鼓励学生主动发表自己的见解，互相探讨、启迪，培养学生勇于探索，敢于创新的精神，引导学生自主学习。此外，教学中还应注意确保学生有充分思考的时间，切实加强学生对问题的认识程度，让高职学生真正感受到对数学的学习并不是那么困难的事情，不断增强学习数学的成功感，增强学习信心，从而优化课堂教学效果。

。

各行的数据是怎么计算出来的呢？

例：用Dijkstra算法求下图从顶点到其余顶点的最短路。

参考文献：

［1］王信峰.计算机数学基础［M］.高等教育出版社，2009.

［2］谢小韦.浅析如何让学生学会学习高职数学［J］.学理论，2010，（36）.

［3］刘志扬.浅谈提高高职数学教学效率的途径和方法［J］.中国科教创新导刊，2011，（7）.