最短路径问题求解.PPT

2007-12-31 第八章 图论 教学目标 通过本章学习，了解图的基本概念，掌握最短路问题的数学模型、解法及其应用，为实际应用奠定基础。 教学内容 第一节图的基本概念 图的定义；路和回路；图G的分类。 第二节最短路问题 狄克斯特拉算法（双标号法）；无向图上的狄克斯特拉算法。 考核知识点及考核要求 1.最短路问题（重点） 领会：最短路问题应用背景； 综合应用：计算具体问题的最短路。 2.图的基本概念（一般） 识记：图的概念，图的分类，链、路与回路。 教学重难点 最短路问题的数学模型、解法及其应用 教学过程 §1 图的基本概念 1.1 图的定义 1、许多现象能用图形表示 例8.1用图表示篮球队比赛情况，如图8-1。此图还表示人与人之间的认识关系；表示工厂间业务往来关系。 例8.2 图8-2是一个石油流向的管网示意图用图表示篮球队比赛情况，如图8-2。此图还表示城市交通网络研究最短路程或运费最省的运输方案。 2、几个常用概念 （1）图G的节点、节点集、不同元素的有序偶或无序偶集合、G的边、G的边集 （2）有向边、无向边、关联、无序节点（a,b）、无序节点a，b （3）一个图可用一个图形来表示且表示是不唯一的。见图8-3 1.2 路与回路 1、路、起点、终点、长度 2、链条、回路 1.3 图G的分类 1.3.1 按G中关联于同一对节点的边数分为多重图和简单图 1、自回路（环）：关联同一节点的一条边 2、平行边（多重边）：关联同一对节点的一条边 3、多重图：含有平行边的图 4、简单图：不含平行边和自环的图 1.3.2 按G的边有序、无序分为有向图、无向图和混合图 1、有向图：每条边都是有向边的图 2、无向图：每条边都是无向边的图 3、混合图：既有无向边又有有向边的图 1.3.3 按G的边有无数量特征分为赋权图和无权图 1、赋权图：附有权数的图 2、无权图：不附有权数的图 1.3.4 按G的任意两个节点有无路分为连通图和不连通图 1、连通图：图的任意两个节点间至少有一条路 2、不连通图：图的任意两个节点间都无一条路 §2 最短路问题（重点）※ 2.1 问题的提出※ 1、最短路径问题 2、最短路径问题求解：贝尔曼最优化原理及其递推方程求解。在阶段明确情况下，用逆向逐段优化枪套推进，这是一种反向搜索法；在阶段不明确情况下，可用函数迭代法逐步正向搜索，直到指标函数衰减稳定得解。 3、用图论分析网络最短路径求解算法。 2.2 狄克斯特拉算法※ 1、狄克斯特拉算法 2、狄克斯特拉算法适用：每条边的权数都大于或等于零的情况。 3、狄克斯特拉算法基本步骤 （1）给起点V1标号（0.1），从V1到V2的距离P（V1）=0，V1为起点。 （2）找出已标号的点集I，没有标号的点集J，求出A=｛（Vi，Vj）︱Vi∈I，Vj∈J｝ （3）若边集A=0计算结束；对已标号的节点求最短路 （4）若A≠o,对于A中每一条边，计算Tij=P（vi）+∪ij，找出边使得Tij=min｛Tij｝. （5）给弧（Vs，Vt）的终点赋予双标号P（Vt）,s） 例8.3 以图8-2给出的石油流向的管道网示意图为例，v1代表石油开采地，v7代表石油汇集地，箭线旁的数字表示管线的长度，现在要从v1地调运石油到v7，怎样选择管线可使路径最短？ 解：见教材第225-226 2.3 无向图上的狄克斯特拉算法 1、无向图中的任一条边（vi,vj）均可用方向相反的两条边（vi,vj）和（vj,vi）来代替。把原来的无向图变为有向图后，即可用上述的狄克斯特拉算法求解。 2、也可在原来无向图上用狄克斯特拉算法求解。在无向图上求解与在有向图上求解的区别在于寻找邻点时不同：在无向图上，只要两节点之间有连线，就是邻点。因此，在无向图上的求解和在相应的有向图上求解相比，计算过程中的邻点个数可能增多，边集合中的边数也就随着增多。计算结束时，一定是所有节点都得到了标号，且其最优结果不会劣于相应有向图的最优结果 本章小结 通过本章学习，了解图的基本概念，掌握最短路问题的数学模型、解法及其应用，为实际应用奠定基础。 作业题 见教材第226第8.1~8.2题 更多自考课件可登陆 /JWDT.html 自考试题中心网址 /STZX.html * LOGO * * *