数学建模最短路问题市公开课一等奖省赛课获奖PPT课件.pptx

该【数学建模最短路问题市公开课一等奖省赛课获奖PPT课件 】是由【guwutang】上传分享，文档一共【71】页，该文档可以免费在线阅读，需要了解更多关于【数学建模最短路问题市公开课一等奖省赛课获奖PPT课件 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第11章 最短路问题
1. 问题提出
2. 图论基本概念
3. 最短路问题求解算法
4. 建模实例
第1页
§1 问题提出
某学校行政部门u0经常有些人到7个部门办事，希望在现有道路网络中确定他们行走路线，使他们到各部门旅程最短。
图中已经标明了部门到部门之间距离。
第2页
§2 图论基本概念
图论是离散数学主要分支，在物理学、化学、系统控制、电力通讯、编码理论、可靠性理论、科学管理、电子计算机等各个领域都含有极其广泛应用。
图论历史能够追溯到1736年，这一年发表了图论第一篇论文，处理了著名哥尼斯堡（Königsberg）七桥问题。
第3页
Königsberg七桥问题
哥尼斯堡城中有七座桥将普雷格尔(Pregel)河中两个岛与河岸联结起来，当初人们热衷于这么一个问题：一个人能否从四块陆地中任何一块出发走过七座桥，每座桥恰走一次，最终回到起点？
(a)
A
B
C
D
A
B
C
D
(b)
第4页
图论基本概念
1. 图定义
G=(V, E,ψ)
顶点，边，e与v连接，v与e关联，相邻，环，重边，平面图，完全图（完备图），二部图（偶图），子图，生成图。
与一个顶点vi关联边数目称为vi度（或次）。
路、圈和连通
有向图、赋权图
第5页
图论一个定理
定理：∑d(v)=2|E|
v∈V
证：因为每一条边提供给点度为2，所以图中全部点度数总和是边数2倍。
推论：在任何图中，奇点个数为偶数。
第6页
2. 图矩阵表示
对于任意图G，定义一个n×m阶矩阵M=（mij）n×m(n为顶点数，m为边数)，其中mij是vi和ej相关联次数（0, 1或2等），该矩阵称为G关联矩阵。
图另一个表示形式是邻接矩阵A=（aij）n×n，其中aij是连接ai和aj边数目。
第7页
图矩阵表示
关联矩阵 邻接矩阵
第8页
§3最短路问题求解算法
设G为赋权有向图或无向图，G边上权均非负。
1. Dijkstra Algorithm: 求G中从顶点u0到其余顶点最短路。
定义：
对每个顶点v，定义两个标号l(v), z(v), 其中l(v)为从u0到v路长； z(v)为v父亲点（前一个点）。
S：含有永久标号顶集。
算法过程就是在每一步改进这两个标号，最终l(v)为u0到v最短路长。输入带权邻接矩阵（距离矩阵）w(u, v).
第9页
最短路问题求解算法
Dijkstra Algorithm
Dijkstra算法所需时间与n2成正比。
第10页