第14节最短路问题与货郎担问题.ppt

1 23 第14节最短路问题与货郎担问题 主要内容 图的矩阵表示带权图最短路问题货郎担问题 2 23 图的矩阵表示 定义1设无向图G V E V v1 v2 vn E m n n的矩阵A aij 称为G的相邻矩阵 其中 性质 4 A的主对角线上的元素全为0 3 23 定理1设A为无向图G的相邻矩阵 V v1 v2 vn 为顶点集 则A的l次幂Al l 1 中元素 为G中vi到vj长度为l的通道的条数 为vi到自身长度为l的闭通道数 图的相邻矩阵 说明 定理1的结论得出的是G中vi到vj长度为l的通道的条数 而不是G中vi到vj长度为l的路的条数 4 23 例1 如图所示 求v1到v3长度为4的通路数 v1到v1长度为4的闭通路数 解相邻矩阵A如下 例题 5 23 例题 从矩阵A4可以看出 v1到v3长度为4的通路数为4 具体为 v1v2v4v2v3 v1v2v3v2v3 v1v4v1v2v3 v1v2v1v2v3 v1到v1长度为4的闭通路数为7 具体为 v1v4v1v4v1 v1v4v2v4v1 v1v4v1v2v1 v1v2v1v2v1 v1v2v4v2v1 v1v2v3v2v1 v1v2v1v4v1 6 23 图的关联矩阵 定义2设无向图G V E V v1 v2 vn E e1 e2 em n m的矩阵M mij 称为G的关联矩阵 其中 性质 vi与ej关联否则 7 23 例2 如图所示 求其关联矩阵 解关联矩阵M如下 例题 8 23 图的连通矩阵 定义3设无向图G V E V v1 v2 vn n n的矩阵P pij 称为G的连通矩阵 其中 性质 1 P的主对角线上的元素全为1 2 若G是连通图 则P中元素全为1 vi与vj之间有路否则 9 23 例3 如图所示 求其连通矩阵 解连通矩阵M如下 例题 10 23 有向图的矩阵表示 1 邻接矩阵2 关联矩阵3 可达矩阵 11 23 定义4设G V E 是一个图 f是V到集合S的一个映射 则称三元组 V E f 是一个顶点带权图 仍记为G V E f v V f v 称为顶点v的权 带权图 12 23 定义5设G V E 是一个图 g是边集E到集合T的一个映射 则称三元组 V E g 为边带权图 也仍记为G V E g x E g x 称为边x的权 带权图 13 23 最短路问题 设G V E 是一个边带权图 权函数g是E到非负实数集R的映射 设H是G的一个子图 则H的权记为g H g H 是指H的各边的权之和 即 所谓最短路问题 就是求边带权无向图中两个给定顶点间的路上各边权之和最小的路 其中E H 为H的边集 14 23 最短路问题 最短路问题是一个优化问题 属于网络优化和组合优化的范畴 对这种优化问题的解答一般是一个算法 最短路问题有很多算法 其中最基本的一个是Dijkstra算法 Dijkstra算法基本思想 若路P u0u1 uk 1uk是从u0到uk的最短路 则P u0u1 uk 1必是u0到uk 1的最短路 基于这一原理 算法由近及远地逐次求出u0到其它各点的最短路 15 23 Dijkstra算法 1 初始化 置h u0 0 v V 若v u0 则置h v S u0 i 0 2 若V S 则 v V S做h v min h v h ui g uiv 4 S S ui 1 i i 1 5 转到步骤2 若V S 停止 3 16 23 实例 求v1到其它各点的最短路径长 17 23 实例 18 23 实例 19 23 最短路问题 说明 1 Dijkstra算法适用于有向带权图 2 Dijkstra算法适用于权值为非负的带权图 3 Dijkstra算法对于求解给定点到其它各顶点的最短路问题是最好的 目前而言 求解图中任意两点之间的最短路问题另有算法 20 23 货郎担问题 货郎担问题也叫旅行商问题 即TSP问题 TravelingSalesmanProblem 是数学领域中著名问题之一 货郎担问题属于易于描述但难于解决的著名难题之一 至今世界上还有不少人在研究它 货郎担问题的基本描述是 某售货员要到若干个村庄售货 各村庄之间的路程是已知的 为了提高效率 售货员决定从所在商店出发 到每个村庄售一次货然后返回商店 问他应选择一条什么路线才能使所走的总路程最短 21 23 货郎担问题 旅行商问题的基本描述是 假设有一个旅行商人要拜访n个城市 他必须选择所要走的路径 路经的限制是每个城市只能拜访一次 而且最后要回到原来出发的城市 路径的选择目标是要求得的路径路程为所有路径之中的最小值 设G V E W 为一个n阶完全带权图Kn 各边的权非负 且有的边的权可能为 求G中的一条最短的哈密顿圈 货郎担问题的数学描述 模型 22 23 货郎担问题 用穷举法解货郎担问题算法的复杂度为 n 1 当n较大时 计算量大的惊人 货郎担问题 的应用领域包括 如何规