数学建模与数学实验 最短路问题

实验目的1、了解最短路的算法及其应用 2、会用Matlab软件求最短路

实验内容1、图 论 的 基 本 概 念

2、最 短 路 问 题 及 其 算 法3、最 短 路 的 应 用

4、建模案例：最优截断切割问题5、实验作业

图论的基本概念一、 图 的 概 念 1、图的定义 2、顶点的次数

3、子图二、 图 的 矩 阵 表 示

1、 关联矩阵2、 邻接矩阵

返回

图的定义定义 有序三元组G=(V,E,

)称为一个图.

[1] V= {v1 , v 2 , , v n } 是有穷非空集，称为顶点集， 其中的元素叫图 G 的顶点 . [2] E 称为边集，其中的元素叫图 G 的边 . [3] 是从边集 E 到顶点集 V 中的有序或无序的元素 偶对的集合的映射，称为关联函数. 例 1 设 G=(V ,E, ),其中 V={v 1 ,v 2 , v3 , v4 }, E={e1 , e2 , e3 , e4, e5 }, (e1 ) v1v2 , (e2 ) v1v3 , (e3 ) v1v4 , (e4 ) v1v4 , (e5 ) v3 v3 .G 的图解如图.

定义 在图 G 中，与 V 中的有序偶(vi, vj)对应的边 e,称为图的有向边(或弧) ,而与 V 中顶点的无序偶 vivj 相对应的边 e,称为图 的无向边 .每一条边都是无向边的图，叫无向图；每一条边都是 有向边的图，称为有向图；既有无向边又有有向边的图称为混 合图.

定义 若将图 G 的每一条边 e 都对应一个实数 w(e),称 w(e)为边的权，并称图 G 为赋权图.

和 分别表示图的顶点数和边数. 规定用记号

常用术语： (1) 端点相同的边称为环. (2) 若一对顶点之间有两条以上的边联结，则这些边称为重边. (3) 有边联结的两个顶点称为相邻的顶点，有一个公共端点的边 称为相邻的边. (4) 边和它的端点称为互相关联的. (5) 既没有环也没有平行边的图，称为简单图. (6) 任意两顶点都相邻的简单图，称为完备图，记为 Kn,其中 n 为顶点的数目. ( 7)若 V=X Y,X Y= ,X 中任两顶点不相邻，Y 中任两顶 点不相邻，称 G 为二元图；若 X 中每一顶点皆与 Y 中一切顶点 相邻，称为完备二元图，记为 Km,n,其中 m,n 分别为 X 与 Y 的顶 点数目.

返回

顶点的次数定义 (1)在无向图中，与顶点 v 关联的边的数目(环算两次) 称为 v 的次数，记为 d(v). (2)在有向图中，从顶点 v 引出的边的数目称为 v 的出度， 记为 d+(v),从顶点 v 引入的边的数目称为的入度，记为 d-(v), d(v)=d+(v)+d-(v) 称为 v 的次数.

d (v4 ) 4

d (v4 ) 2 d (v4 ) 3 d (v4 ) 5

定理1

v V (G )

d (v) 2 (G)

推论1 任何图中奇次顶点的总数必为偶数.

例 在一次聚会中，认识奇数个人的人数一定是偶数。

返回

子图定义 设图 G=(V,E, ),G1=(V1,E1,

1 )

e E1 时， 1 (e)= (e),则称 G1 是 G 的子图. V,E (1) 若 V1 E,且当 1 特别的，若 V1=V,则 G1 称为 G 的生成子图.

V,且 V1 ,以 V1 为顶点集、两个端点都在 V1 中的 (2) 设 V1 图 G 的边为边集的图 G 的子图，称为 G 的由 V1 导出的子图，记为 G[V1].(3)设 E1 E,且 E1 ,以 E1 为边集,E1 的端点集为顶点集的图 G 的子图, 称为 G 的由 E1 导出的子图,记为 G[E1].

G

G[{v1,v4,v5}]

G[{e1,e2,e3}]

返回

关联矩阵对无向图G,其关联矩阵M=(mij ) ,其中：

1 mij 0

若vi 与e j 相关联 若vi 与e j 不关联

注：假设图为简单图

e1 1 M= 1 0 0

e 2 e3 e 4 e 5 0 0 0 1 v1 1 0 1 0 v2 0 1 1 0 v3 1 1 0 1 v4

对有向图G,其关联矩阵M=(mij ) ,其中：

1 mij 1 0

若vi 是e j的起点 若vi 是e j的终点 若vi 与e j 不关联

返回

邻接矩阵对无向图G,其邻接矩阵 A (aij ) ,其中：

1 aij 0

若vi 与v j 相邻 若vi 与v j 不相邻 A=

注：假设图为简单图v1 v2 v3 v4 0 1 0 1 v1 1 0 1 1 v2 0 1 0 1 v3 1 1 1 0 v4

对有向图G=(V,E) ,其邻接矩阵 A (aij ) ,其中：

1 aij 0

若( vi,v j) E 若( vi,v j) E

对有向赋权图G,其邻接矩阵 A (aij ) ,其中：

wij aij 0

若(vi , v j ) E , 且wij为其权 若i j 若(vi , v j ) E

无向赋权图的邻接矩阵可类似定义.

v1 v2 v3 v4 0 2 7 v1 A= 2 0 8 3 v2 8 0 5 v 3 7 3 5 0 v 4返回

最短路问题及其算法一、 基 本 概 念 二、固 定 起 点 的 最 短 路 三、每 对 顶 点 之 间 的 最 短 路

返回

基 本 概 念定义1 在无向图 G=(V,E, )中： (1) 顶点与边相互交错且 (ei ) v i 1 v i (i=1,2,…k)的有限非空序列

w (v 0 e1 v1 e 2 v k 1 e k v k ) 称为一条从 v0

vk 到

Wv 0 v k 的通路，记为

Tv0vk (2)边不重复但顶点可重复的通路称为道路，记为 Pv 0 v k (3)边与顶点均不重复的通路称为路径，记为通路 W v1v4 v1 e 4 v 4 e5 v 2 e1 v1 e 4 v 4 道路 Tv1v4 v1 e1 v 2 e5 v 4 e 6 v 2 e 2 v 3 e3 v 4 路径 Pv1v4 v1 e1 v 2 e5 v 4

定义2 (1)任意两点均有路径的图称为连通图. (2)起点与终点重合的路径称为圈. (3)连通而无圈的图称为树.

定义3 (1)设 P(u,v)是赋权图 G 中从 u 到 v 的路径， 则称 w( P ) e E ( P )

w(e) 为路径 P 的权.

(2)

在赋权图 G 中，从顶点 u 到顶点 v 的具有最小权的路

P * (u , v ) ,称为 u 到 v 的最短路.

返回

固 定 起 点 的 最 短 路最短路是一条路径，且最短路的任一段也是最短路. 假设在u0-v0的最短路中只取一条，则从u0到其 余顶点的最短路将构成一棵以u0为根的树.

因此, 可采用树生长的过程来求指定顶点到其余顶点 的最短路.

Dijkstra 算法：求 G 中从顶点 u0 到其余顶点的最短路 设 G 为赋权有向图或无向图，G 边上的权均非负.对每个顶点，定义两个标记(l (v) ,z(v ) ) ,其中:

l (v) :表从顶点 u0 到 v 的一条路的权. z(v ) :v 的父亲点，用以确定最短路的路线算法的过程就是在每一步改进这两个标记，使最终 l (v) 为从顶点 u0 到 v 的最短路的权.

S:具有永久标号的顶点集输入: G 的带权邻接矩阵w(u, v)

算法步骤：(1)赋初值：令 S={ u0 }, l (u0 ) =0

v S V \ S ,令l (v) =W (u0 , v) ,z(v ) u =0 u u 0 (2)更新 l (v) 、z(v ) : v S V \ S ,若 l ( v ) > l ( u) W ( u, v ) 则令l (v) = l (u) W (u, v ) ,z(v ) u=S (3) 设v 是使l (v) 取最小值的 u v**

v{ 中的顶点，则令 S=S∪

*

},

(4) 若S φ ,转 2,否则，停止.

v 到 的最短路的权，从 v 用上述算法求出的 l ( v ) 就是u0 的父亲标记 z ( v ) 追溯到u0 , 就得到u0v到 的最短路的路线.

例 求下图从顶点 u1 到其余顶点的最短路. TO MATLAB

(road1)

先写出带权邻接矩阵：

0 2 1 8 0 6 1 0 7 0 5 W 0

1 3 0

9 2 4 0

9 6 3 0

因 G 是无向图，故 W 是对称阵.

迭代 次数 1 2 3 4 5 6 7 8 最后标记 : l (v )

l (u i ) u 5 u6 u7 u8 u1 u 2 u 3 u 4 0 0 2 1 8 2 8 10 8 3 10 8 6 10 12 7 10 12 9 12 12

z (v )

u1 u1

0

2

u1

1

u 67

u2 3

u5 6

u 49

12 u 5