数学建模最短路问题

G
G[{v1,v4,v5}]
G[{e1,e2,e3}]
返回
关联矩阵
对无向图Ｇ，其关联矩阵Ｍ＝ (mij ) ，其中：
1 mij 0
若vi与e
相关联
j
若vi与e
不关联
j
注：假设图为无向简单图
e1 e2 e3 e4 e5
1 0 0 0 1 v1
M= 1 1 0 1 0 v2
0 0
0 1
1 1
1 0
算法的过程就是在每一步改进这两个标记，使最终 l(v) 为从顶点 u0 到 v 的最短路的权．
S：具有永久标号的顶点集
输入: G 的带权邻接矩阵 w(u, v)
算法步骤：
（１）赋初值：令 S＝{ u0 }, l(u0 ) =0 v S V \ S ,令 l(v) =W(u0 ,v) , z(v) = u0 u u0
• Euler把南北两岸和四个岛抽象成四个点,将连接这些 陆地的桥用连接相应两点的一条线来表示,就得到如下 一个简图:
A
N
S
B
欧拉的结论
• 欧拉指出:一个线图中存在通过每边一次仅一次 回到出发点的路线的充要条件是:
• 1)图是连通的,即任意两点可由图中的一些边连接 起来;
• 2)与图中每一顶点相连的边必须是偶数.
（２）在有向图中，从顶点 v 引出的边的数目称为 v 的出度， 记为 d＋(v) ，从顶点 v 引入的边的数目称为 v 的入度，记为d－(v) ，
d (v) = d＋(v) + d－(v) 称为 v 的次数．
d(v4 ) 4
d (v4 ) 2 d (v4 ) 3 d (v4 ) 5
定理１ d(v) 2 (G) vV (G)

设链W=v0e1v1e2…eivi已选定，则从E\{e1,e2,…,ei}中选取一条与ei相邻的边ei+1，除非已无选择余地，否则不要选G\{e1,e2,…,ei}的桥。
直到(2)不能进行为止，算法终止时得到的是Euler回路。
欧拉图与Fleury算法
01
02
如果G不是连通的Euler图，则G中含有奇度顶点（但奇度顶点的个数为偶数），此时图G的一条邮递路线必定在某些街着上重复走了一次或多次，它等价于在这些边上加一条或多条重复边，使新图G' 不含奇度顶点，并且所加边的总权为最小。
01
Dijkstra Algorithm
02
Dijkstra算法所需时间与n2成正比。
最短路问题求解算法
用Dijkstra求解最短路问题
例 求从顶点u0到其余顶点的最短路。
解：先写出距离矩阵（实际应为对称矩阵）
Dijkstra算法的迭代步骤如下
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 6 7 10 12 7 9 12 8 12
第11章 最短路问题
添加副标题
1 问题的提出
STEP2
STEP1
图论是离散数学的重要分支，在物理学、化学、系统控制、电力通讯、编码理论、可靠性理论、科学管理、电子计算机等各个领域都具有极其广泛的应用。
1
图论的历史可以追溯到1736年，这一年发表了图论的第一篇论文，解决了著名的哥尼斯堡（Königsberg）七桥问题。
02
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的最大匹配。

网 络 优 化
Network Optimization
/netopt
清华大学课号：40420213（本），70420133（研）
第5章 最短路问题(Shortest Path Problem)
清华大学数学科学系 谢金星 办公室：理科楼1308# （电话：62787812） Email:jxie@ /faculty/~jxie
u s 0, u min{u w }. i ij j i j
一般情况下直接求解最短路方程是相当困难的.
(5.7) (5.8)
10
最短路树（树形图）
定理5.1 对于只含正有向圈的连通有向网络，从起点s到任一顶 点 j 都存在最短路，它们构成以起点 s 为根的树形图（称为最短 路树（Tree of Shortest Paths）或最短路树形图（Shortest Path Arborescence）），最短路的长度可以由Bellman方程唯一确定.
1
最短路问题的例子和意义
S
T
许多实际问题都可以转化为最短路问题
其有效算法经常在其它网络优化问题中作为子算 法调用
2
最短路问题的例子 - 单产品、无能力限制的批量问题
例5.1 （Single-level Uncapacitated Lotsizing） 某工厂生产某种产品用以满足市场需求,且已知在时段t中的市 场需求为dt . 在某时段t, 如果开工生产, 则生产开工所需的生 产准备费为st , 单件产品的生产费为ct .在某时段t期末, 如果有 产品库存, 单件产品的库存费为ht . 假设初始库存为0, 不考虑 能力限制, 工厂应如何安排生产, 可以保证按时满足生产, 且 使总费用最小? （Wagner – Whitin，1958） 假设在时段t, 产品的生产量为xt , 期末产品的库存为It (I0 =0); 用二进制变量yt表示在时段t工厂是否进行生产准备. T T 假设费用均非负，则在最优解中 I 0 I T 0 ，即 xt d t

M= 1 1 0 1 0 v2

0 0
0 1
1 1
1 0
0 1

v3 v4
对有向图Ｇ，其关联矩阵Ｍ＝ (mij ) ，其中：
1 mij 1
0
若vi
是e
的起点
j
若vi
是e
的终点
j
若vi与e j不关联
返回
邻接矩阵
对无向图Ｇ，其邻接矩阵 A (aij ) ，其中：
v1
e1
v2
e4
e5 e2
v4
e3
e6 v3
v5
e7
e8
v7 e9
v6
情形２ G 有２n 个奇次顶点（n ２）
Edmonds 最小对集算法：
基本思想：
先将奇次顶点配对，要求最佳配对，即点对之间距离总和 最小．再沿点对之间的最短路径添加重复边得欧拉图 G*，G*的 欧拉巡回便是原图的最佳巡回．
算法步骤：
C= v1,v2,… ,vi,,vj , vj-1,… , vi+1,vj+1, …,vn,v1 (3)对 C 重复步骤(2)，直到条件不满足为止，最后得到的 C 即 为所求．
例 对以下完备图，用二边逐次修正法求较优H圈．
返回
数学建模与数学实验 最短路问题
实验目的 实验内容
1．了解最短路的算法及其应用 2．会用MATLAB软件求最短路
中．
欧拉图
定义１ 设 G=(V,E)是连通无向图 （１）经过 G 的每边至少一次的闭通路称为巡回． （２）经过 G 的每边正好一次的巡回称为欧拉巡回． （３）存在欧拉巡回的图称为欧拉图． （４）经过 G 的每边正好一次的道路称为欧拉道路．