文档介绍：Email:******@swufe.
图论算法
数值计算
搜索法、最速下降……
规划方法
单纯型法、匈牙利算法……
非数值运算
搜索法、图论算法、组合优化……
现代优化方法
遗传算法、蚁群算法、神经网络……
算法分析
哥尼斯堡七桥问题
从某点出发通过每座桥且每桥只通过一次回到起点
D
A
B
C
一、图的一般理论
1、起源
A
B
C
D
建模:
点——陆地岛屿
边——桥
一个图G由一个顶点集V和一个边的集E组成。
E中每个元素e是连接顶点集 V中两个顶点u和v的边。
例:
图G=<V,E>:
点集 V = {v1,v2, ...,vn}
边集 E = {e1,e2, ...,em} 其中 ek=vivj
图G=<V,E>:
其中 V = {v1,v2,v3,v4,v5}
E = {e1,e2,e3 ,e4}
e1=v1v2,e2=v2v4,e3=v1v4,e4=v5v2
e1
v1
v2
v3
v4
v5
e2
e3
e4
2、定义
图的图形表示
例
联接
点的位置, 边的长度
×
v1
v2
v3
v4
v5
e1
e2
e3
e4
比较: 同构
G1
G2
G3
1
2
3
4
3
4
2
1
3
4
1
2
v1
v2
v3
v4
v5
e2
e3
e4
例
(1)邻接矩阵(点点)
3、矩阵表示
v1
v2
v3
v4
v5
e1
e2
e3
e4
e5
e6
e7
e8
例
(2)关联矩阵(点边)
v1
v2
v3
v4
v5
e1
e2
e3
e4
e5
e6
e7
e8
例
4、连通性
邻
接
长2
通路:
长3
长n-1
连通矩阵
v1
v2
v3
v4
v5
e1
e2
e3
e4
e5
e6
e7
e8
二、最短路问题
1、单源最短路问题——Dijkstra
赋权图G
从点v0到其余结点的通路——权和最小
Dijkstra算法思想
按路径长度递增顺序求最短路径算法
两个集合:S已求得最短路径的结点、V-S未确定 
每一步:将S 与V-S之间最短路经终点加入S
存储
G:带权邻接矩阵
每点标记(dj, pj):至j点最短路径的长度、前一点
Dijkstra算法流程
赋初值:w,
各点与源点之间:已求S={v0},
最短长度d=w(v0,:)、前一点p= v0
u= v0
更新d、p:
若d(i)>d(u) +w(u,i),则d(i)=d(u) +w(u,i),p(i)=u
寻找v:
V-S中使d(i)最小的v: S=S{v}, u= v
若V-S,重复2,
否则:结束
v0
v
u
d(v)
d(u)
w(u,v)