运筹学 教案
标题：标号法求最短路径问题 教学目标： 1.通过本节学习，使学生掌握标号法的步骤； 2.通过本节学习，学生能够应用标号法求解配送路径问题 教学重点及难点： 重点：标号法的求解步骤；难点：标号法在配送路径问题中的应用 教 学 内 容 （教 学 时 数：2 ） 一、标号法的概念 标号法也称Dijstra算法，是荷兰科学家Dijstra于1959年提出的求解指定两点间最短路径的有效算法。 二、标号法的适用范围和原理 条件：网络中所有的边（弧）的权重值 wij≥0； 范围：指定两点间或指定一点到另一点的最短路径问题； 原理：最短路的子路还是最短路。 三、标号法的思想 备注： 从起点vs开始，逐步给每个结点vj标号[dj ,vi]，其中dj为起点 vs到vj的最短距离， vi为该最短路线上的前一节点。 若给终点vt标上号[dt ,vi], 表示已求出v1至vt的最短路其最短路长为dt，最短路径可根据标号vi反向追踪而得。 四、标号法的求解步骤
备注： 五、例题讲解与练习 求解过程详见PPT。 练习：利用标号法求V1到V8的最短路径 作业、讨论题、思考题：完成课本158页的第1、2题
因篇幅问题不能全部显示，请点此查看更多更全内容
Copyright © 2019- jqkq.cn 版权所有 赣ICP备2024042794号-4
违法及侵权请联系：TEL:199 1889 7713 E-MAIL:2724546146@qq.com
本站由北京市万商天勤律师事务所王兴未律师提供法律服务