数学建模最短路

求G中从顶点u0到其余顶点
定义：
对每个顶点v，定义两个标号l(v), z(v), 其中l(v)为从 u0到v的路长； z(v)为v的父亲点（前一个点）。
S：具有永久标号的顶集。
算法的过程就是在每一步改进这两个标号，最终 l矩(v阵)为）u0w到(uv,的v)最. 短路长。输入带权邻接矩阵（距离
9
例 已知距离矩阵为
0 9 5 8
W
6 6 7
0 5
6 0 10
14 0
求任意两点之间的最短路。
14
Floyd Algorithm
解：D(0)=W, P(0)=(0)n×n
0 9 5 8
D
(1 )
6 6 7
0 5 16
6 0 10
14 14 0
,
0 0 0 0
P
(1 )
(3)设v*是使l(v)取最小值的 S中的顶点,则令S S {v*}, u v*
(4)若S ,转(2);否则,停止.
Dijkstra算法所需时间与n2成正比。
10
用Dijkstra求解最短路问题
例 求从顶点u0到其余顶点的 最短路。
解：先写出距离矩阵（实际 应为对称矩阵）
0 2 1 8
推论：在任何图中，奇点个数为偶数。
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 的边的数目。
最短路问题求解算法
Dijkstra Algorithm
(1)赋初值:令S {u0},l(u0) 0,vS V \ S, 令l(v) , z(v) , u u0
(2)更新l(v),z(v):vS V \ S,若l(v) l(u) w(u,v), 则令l(v) l(u) w(u,v), z(v) u
第11章 最短路问题
1. 问题的提出 2. 图论的基本概念 3. 最短路问题求解算法 4. 建模实例
1
§1 问题的提出
某学校行政部门u0经 常有人到7个部门办 事，希望在现有的道 路网络中确定他们行 走的路线，使他们到 各部门的路程最短。
图中已经标明了部门 到部门之间的距离。
2
§2 图论的基本概念
7
图的矩阵表示
关联矩阵 邻接矩阵
2 1 0 0 1v1 M0 1 1 1 0v2
0 0 1 1 1v3
ee e e e 12345
1 1 1v1 A1 0 2v2
1 2 0v3
v1 v2 v3
8
§3最短路问题求解算法
设G为赋权有向图或无向图，G边上的权均非负。
1. Dijkstra Algorithm: 的最短路。
图论是离散数学的重要分支，在物理 学、化学、系统控制、电力通讯、编 码理论、可靠性理论、科学管理、电 子计算机等各个领域都具有极其广泛 的应用。
图论的历史可以追溯到1736年，这一 年发表了图论的第一篇论文，解决了 著名的哥尼斯堡（Königsberg）七桥 问题。
3
Königsberg七桥问题
最大号码，pij=0，表示无中间节点， (1)赋初值：dij= wij, pij = 0, k = 1 (2)更新dij, pij：对所有i, j，若dik+dkj< dij，则
dij = dik+dkj, pij = k (3)若k = n，停止；否则k = k+1, 转(2).
13
Floyd Algorithm
6
7
10 12
7
9 12
8
12
最后标记：
l(v) 0 2 1 7 3 6 9 12
z(v)u0 u0 u0 u5 u1 u4 u3 u4
最短路问题求解算法
2. Floyd Algorithm (1962): 求任意两点间的最 短路。
D =（dij）n×n, dij是i到j的最短路长， P =（pij）n×n, pij是i到j的最短路上中间节点的
哥尼斯堡城中有七座桥将普雷格尔(Pregel) 河中的两个岛与河岸联结起来，当时人们热 衷于这样一个问题：一个人能否从四块陆地 中的任何一块出发走过七座桥，每座桥恰走 一次，最后回到起点？
A
A
C
D
B (a)
C
D
B
(b)
4
图论的基本概念
1. 图的定义
G=(V, E,ψ) 顶点，边，e与v连接，v与e
§1 匹配与覆盖 1. 基本概念 定义1设若M的边互不相邻，则称M是G的一个
匹配。M的边称为匹配边，E\M的边称为自由 边，若(u, v)∈M，则称u（或v）是v（或u）的 配偶。若顶点v与M的一条边关联，则称v是M饱和的；否则称为M-非饱和的。若M使G中每 个顶点都是M-饱和的，称M是G的完美（理想） 匹配。设M是G的一个匹配，若不存在M' 使 |M'|>|M|，则称M为G的最大匹配。
P (4) P (3)
建模案例分析
2000B题 钢管订购和运输
16
2000B钢管运输分析求解步骤
1.用Floyd算法求出铁道两点间的最短 路长，将路长转成费用。
2.与公路运价组成的矩阵D，再用 Floyd求出S1,…,S7到A1,…,A15的最短 路，将购买单价计入运费之中。
18
第12章 匹配与覆盖及其应用
关联，相邻，环，重边， 平面图，完全图（完备 图），二部图（偶图）， 子图，生成图。 与一个顶点vi关联的边的数 目称为vi的度（或次）。 路、圈和连通 有向图、赋权图
5
图论的一个定理
定理：∑d(v)=2|E|
v∈V
证：因为每一条边提供给点的度为2， 所以图中所有点的度数总和是边数的2 倍。
0 6 1
0
7
9
W
0 5 1 2
0
3
9
0 4 6
0 3
0
11
Dijkstra算法的迭代步骤如下
迭代
l(ui)
次数 u0 u1 u2 u3 u4 u5 u6 u7
1 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞
2
2 1 8 ∞ ∞∞∞
3
2
8 ∞ ∞ 10 ∞
4
8 3 ∞ 10 ∞
5
8
6 10 12
0 0 0
0 0 1
0 0 0
1
0 0
0 9 5 8
D
(2)
6 6 7
0 5 16
6 0 10
14 14 0
,
P (2) P (1)
0 9 5 8
D
(3)
6 6 7
0 5 15
6 0 10
14 14 0
,
0 0 0 0
P
源自文库
(3)
0 0 0
0 0 3
0 0 0
1
0 0
D (4) D (3),