图与网络分析到最短路问题.ppt

第1页 第六章 图与网络分析 图的基本概念与模型 树图和图的最小部分树 最短路问题 网络最大流问题 最小费用最大流问题 第2页 第八章 图与网络分析 图的基本概念与模型 树图和图的最小部分树 最短路问题 网络最大流问题 最小费用最大流问题 第3页 图论是应用非常广泛的运筹学分支，它 已经广泛地应用于物理学控制论，信息论， 工程技术，交通运输，经济管理，电子计算 机等各项领域。对于科学研究，市场和社会 生活中的许多问题，可以同图论的理论和方 法来加以解决。例如，各种通信线路的架设 ，输油管道的铺设，铁路或者公路交通网络 的合理布局等问题，都可以应用图论的方法 ，简便、快捷地加以解决。 引 言 第4页 1736年瑞士科学家欧拉发表了关于图论方面的第 一篇科学论文，解决了著名的哥尼斯堡七座桥问题。 即一个漫步者如何能够走过这七座桥，并且每座桥只 能走过一次，最终回到原出发地。如图1所示。 引例1 欧拉将这个问题抽象成一笔画问 题。即能否从某一点开始不重复 地一笔画出这个图形，最终回到 原点。欧拉在他的论文中证明了 这是不可能的，因为这个图形中 每一个顶点都与奇数条边相连接 ，不可能将它一笔画出，这就是 古典图论中的第一个著名问题。 第5页 在实际的生产和生活中，人们为了反映事物之间 的关系，常常在纸上用点和线来画出各式各样的示意 图。 引例2 左图是我国北京、上海、重庆等 十四个城市之间的铁路交通图， 这里用点表示城市，用点与点之 间的线表示城市之间的铁路线。 诸如此类还有城市中的市政管道 图，民用航空线图等等。 连云港 武汉南京 徐州 上海 北京塘沽 青岛 济南 天津 郑州 第6页 有六支球队进行足球比赛，我们分别用点 v1v6表示这六支球队，它们之间的比赛情况，也 可以用图反映出来，已知v1队战胜v2队，v2队战胜 v3队，v3队战胜v5队，如此等等。这个胜负情况， 可以用下图所示的有向图反映出来。 引例3 v3 v1 v2 v4 v6 v5 第7页 图的基本概念与模型 点：研究对象（车站、国家、球队）； 点间连线：对象之间的特定关系（陆地间有桥、铁 路线、两球队比赛及结果)。 对称关系：桥、道路、边界；用不带箭头的连线表 示，称为边。 非对称关系：甲队胜乙队，用带箭头的连线表示， 称为弧。 图：点及边（或弧）组成。 注意：一般情况下，图中的相对位置如何，点与点之间线 的长短曲直，对于反映研究对象之间的关系，显的并不重 要，因此，图论中的图与几何图，工程图等本质上不同。 第8页 对 称 关 系 非 对 称 关 系 无向图：图由点和边所构成的， 记作G = = V ,E(V是点的集合，E是边的集合) 连接点vi,vjV的边记作eij=vi,vj，或者vj,vi。 有向图：图是由点和弧所构成的， 记作D=V ,A(V是点的集合，A是弧的集合) ， 一条方向从vi指向vj的弧，记作(vi,vj)。 图的相关概念 网络图：给图中的点和边赋予具体的含义和权数，如距离， 费用，容量等，记作N. 第9页 图的相关概念 若边eij=vi,vjE，称vi，vj是eij的端点，也称vi，vj 是相邻的。称eij是点vi（及点vj）的关联边。 若两条边有一个公共的端点，则称这两条边相邻。 vivj e vi，vj相邻 e 与vi，vj关联 vi e1 vj vk e2 点与边关联 点与点 相邻边与边相邻 第10页 若某条边两个端点相同，称这条边为环。 若两点之间有多于一条的边，称这些边为多重边。 无环、无多重边的 图称为简单图。 无环、但允许有多 重边的图称为多重 图。 v1 e1e2 e3 v2 v3 e5 e4 v4 v5 注：无特别声明我们今后讨论的图都是简单图 图的相关概念 第11页 图G中以点v为端点的边的数目，称为v在G中的 次(度）， 记为d（v）。 d(v1)=2 d(v2)=3 d(v3)=4 d(v4)=1 次为1 的点为悬挂点，悬挂点的关联边称为悬 挂边，次为零的点称为孤立点。 v1 e1e2 e3 v2 v3 e5 e4 v4 v5 次为奇数的点称为奇点，否则称为偶点。 图的相关概念 第12页 给定图G=（V，E），若图G=（V，E），其中 VV，E E ，则称G是G的子图。 给定图G=（V，E），若图G=（V，E），其中EE ，则称G是G的一个支撑子图（部分图）。 点全部保留 （a） （b） 子图 （c） 部分图 子图与部分图（支撑子图） 第13页 图的连通性 链：设图G=（V，E）中有一个点、边交替序 列 v1 ,e1,v2,vn-1,en-1 ,vn，若 ei=(vi,vi+1)，即这(n-1)条边把n个顶点串 连起来，我们称这个交替序列为图G中的一 条链，而称点v1,vn为该链的两个端点。 对于简单图链也可以仅用点的序列来表示。 如果一条链的两个端点是同一个点，则称它为闭链或圈； 如果一条链的各边均不相同，则称此链为简单链； 更若一条链的各点、各边均不相同，则称该链为初等链。 v1v3v5e1e2 v7 v8 e7 v2v4v6 e3e4 e5 e6 e8e9 简单链：1=（v2，v1，v3，v6，v4，v3，v5） 初等链：2=（v2，v1，v3，v5） 第14页 图的连通性 最短链:网络中链上权值的和称为链的长度 ，以点v1,vn为端点的诸链中长度最短的 链称为这两点的最短链。 连通图：如果图G=（V，E）中的任意两点都 是其某一条链的两个端点，则称图G是连 通图，否则，称图G是不连通的。 v1v3v5e1e2 v7 v8 e7 v2v4v6 e3e4 e5 e6 e8e9 为不连通图， 有两个连通分 图组成 第15页 图的矩阵表示 图的矩阵表示主要方法有：权矩阵、邻接矩阵。 权矩阵 网络图N=（V，E），边vi，vj的权为wij ，构造矩阵 称矩阵A为网络N的权矩阵。 v4 v5 v2 v1 v3 2 3 4 5 6 7 8 9 4 其权矩阵为： 注：当G为无向图时，权矩阵为对称矩阵。 第17页 图G=（V，E），p=n，构造矩阵 称矩阵A为G的邻接矩阵。 邻接矩阵 ？ vi与vj不相邻 图的矩阵表示 其邻接矩阵为： v4 v5 v2 v1 v3 注：当G为无向图时，邻接矩阵为对称矩阵。 思考：有甲、乙、丙、丁、戊、己六名运动员报名参加A 、B、C、D、E、F六个项目的比赛，下表中打的是个运动员报 名参加比赛的项目，问六个项目的比赛顺序应如何安排？做到 每名运动员都不连续地参加两项比赛。 A B C D E F 分析：点表示项目，边表示两个项目有同一名运动员参加 目的：在图中找出点序列 ，使得依次排列的两个点 不相邻，就找到了每名运 动员不连续参加两项比赛 的安排方案 A、C、B、F、E、D (不唯一) 第20页 第八章 图与网络分析 图的基本概念与模型 树图和图的最小部分树 最短路问题 网络最大流问题 最小费用最大流问题 第21页 第六章 图与网络分析 图的基本概念与模型 树图和图的最小部分树 最短路问题 网络最大流问题 最小费用最大流问题 第22页 7个村庄要在他们之间架设电话线，要求任何两个村庄都可 以互相通电话(允许中转)，并且电话线根数最少？ 引例 村庄1 村庄4 村庄3 村庄6 村庄2 村庄5 村庄7 分析：用七个点代表村庄，如果在某两个村庄之间架设电 话线，则相应的在两点之间连一条边，这样电话线网就可 以用一个图来表示，并且满足如下要求： 连通图 图中有圈的话，从圈中任去掉一条边，余下的图仍连通 第23页 树 村庄1 村庄4 村庄3 村庄6 村庄2 村庄5 村庄7 如果G=（V，E）是一个无圈的连通图，则称G为树。 树中必存在次为1的点（悬挂点） 树中任两点必有一条链且仅有一条链； 在树的两个不相邻的点之间添加一条边，就得到一个圈； 反之，去掉树的任一条边，树就成为不连通图； n个顶点的树有（n-1）条边。 树是最脆弱的连通图！ 第24页 1 4 5 2 4 1 5 7 5 2 3 7 图的部分树（支撑树 ） 如果图G=（V，E）的部分图G=（V，E）是树， 则称G是G的部分树（或支撑树）。 村庄1 村庄4 村庄3 村庄6 村庄2 村庄5 村庄7 部分树上各树枝上权值的和称为它的长度，其中长度 最短的部分树，称其为该图的最小部分树（最小支撑 树）。 点保留 边可去 仍是树 不唯一 思考：如何铺设电话线，使得电话线长度最少？ 第25页 i j k m l 最小部分树的求法 定理：图中任一个点i，若j是与相邻点中距离最近的， 则 边i,j一定必含在该图的最小部分树内。 推论：把图的所有点分成 和 两个集合，则两集合之 间连线的最短边一定包含在最小部分树内。 避圈法 破圈法 第26页 2 2 7 5 4 1 4 3 5 1 7 5 A B C D E ST 算法的步骤： 1、在给定的赋权的连通图上任选一点vi ,其余点在 中。 2、从 与 的连线中找出权数最小的边vi, vj，这条边一 定包含在最小部分树内，做以标记。 3、令 vj ， ； 4、重复2、3两步，直至所有点都包含在 中为止。 vj 避圈算法 S 第27页 7 7 A B C D E ST 2 2 5 4 1 4 3 5 1 5 破圈算法 算法的步骤： 1、在给定的赋权的连通图上任找一个圈。 2、在所找的圈中去掉一个权数最大的边（如果有两条或 两条以上的边都是权数最大的边，则任意去掉其中一条 ）。 3、如果所余下的图已不包含圈，则计算结束，所余下的 图即为最小生成树，否则返回第1步。 第28页 第六章 图与网络分析 图的基本概念与模型 树图和图的最小部分树 最短路问题 网络最大流问题 最小费用最大流问题 第29页 第八章 图与网络分析 图的基本概念与模型 树图和图的最小部分树 最短路问题 网络最大流问题 最小费用最大流问题 第30页 什么是最短路问题？什么是最短路问题？ 固定起点的最短路 Dijkstra(狄克斯拉) (荷兰)算法：标号法 每 对 顶 点 之 间 的 最 短 路 矩阵算法 最短路问题 第31页 最短路问题提出 在现实生活中，除公路运输网络、电讯网 络等网络图以外，还有输油管线这样的图。在 输油管线图中，为反映油的输送情况，两点间 不仅有连线，线上往往还标有箭头，以表示油 的流动方向。又如，指挥系统图、控制系统图 等图中都标有指向。从这样的一类图中就可以 概括为有向图的概念。 第32页 有向图 由点集 和V 中元素的有序对的一个集合 所组成的二元组称为有向图，记为D=（V，A）。 其中 V中的元素 vi叫做顶点， A中元素aij叫做以vi为始点（尾），vj为终点（ 首）的弧。 aij与aji作为具有不同指向的弧是不同的。 第33页 有向网络与混合图 如果在图D=（V，A）中，给每一弧赋予权值， 如 将弧aij=(vi,vj)有权值 wij，记为w(aij)=wij则 赋权有向图D=（V，A）称为有向网络，在不至 于混淆时，也简称网络。 混合图如果一个图中既有边，也有弧，那么称 这种图为混合图。它往往出现在既有单行线， 又有双行线的交通图中。 1 2 5 3 4 3 7 2 第34页 最短路问题引例 下图为单行线交通网，每弧旁的数字表示通过这条线 所需的费用。现在某人要从v1出发，通过这个交通网 到v8去，求使总费用最小的旅行路线。 v2 v5 2 3 4 6 4 v3 v1 v4 v6 12 10 6 1 2 10 v8 v9 v7 2 36 3 从v1到v8： P1=（v1，v2，v5，v8） 费用 6+1+6=13 P2=（v1，v3，v4， v6， v7， v8） 费用 3+2+10+2+4=21 P3= 从v1到v8的旅行路线 从v1到v8的路。 旅行路线总费用 路上所有弧权之和。 最短路问题中，不考虑有向环、并行弧。 v2 v5 2 3 4 6 4 v3 v1 v4 v6 12 10 6 1 2 10 v8 v9 v7 2 36 3 第36页 几个概念 路：设p是D中一个首尾相连的弧的集合，如果vs是 它的第一条弧的始点，vt是它的最后一条弧的终 点，则称它是以点vs为始点，以点vt为终点的一 条路。 路长：路p中所有弧的权值的和称为路p的长，记 为 设图D=（V，A）是一有向网络 v2 v5 2 3 4 6 4 v3 v1 V4 v6 12 10 6 1 2 10 v8 v9 v7 2 36 3 第37页 设P是以点vs为始点，以点vt为终点的所有路的集合 ， 如果 ,且 ，则称p0是以点 vs 为始点，以点vt为终点的最短路。而称其路长为 点 vi到点vj的距离，记为 。 几个概念 注意：在有向网络中,一般 最短路及一点到另一点的距离 最短路问题是重要的最优化问题之一，可以直接应用于解 决生产实际的许多问题:管道铺设、线路安排、厂区布局等。 而且经常被作为一个基本工具来解决其他的优化问题。 第38页 最短路问题求解方法 Dijkstra算法 矩阵算法 第39页 最短路问题求解方法 Dijkstra算法 矩阵算法 第40页 求解最短路问题的Dijkstra算法 条件：当所有 wij 0 时，用来求给定点vs到任一 个点vj 最短路的公认的最好方法。 事实：如果P是D中从vs到vj的最短路，vi是P中的一 基解 个点，那么，从vs沿P到vi的路是从vs到vi的最 基解 短路。 Dijkstra算法是Dijkstra在1959年提出的，可用于求解 指定两点间的最短路问题，或从指定点到其余各点的最短 路问题。由于其以标号为主要特征，又称为标号法。 v1 v2 v3 v4 v5 最短路的子路是最短路 第41页 Dijkstra算法基本 思想 从始点vs出发，逐步顺序地向外探寻，每向外延伸一步都 要求是最短的。执行过程中，与每个点对应，记录下两个数( 称为这个点的标号) 1.标号 P（固定标号或永久性标号） 从始点vs到该标号点vj的最短路权P (vj) 。 2.标号 T（临时性标号） 从始点vs到该标号点vj的最短路权上界T (vj) 。 j ,P (vj) j, T (vj) 该方法的每一步就是去修改T标号，并且把某一个具T标号的点 改变为具有P标号的点，从而使D中具P标号的顶点数多一个， 至多经过n-1步，就可以求出始点vs到各点的最短路。 前点标号j 表示始点vs到vj的最短路上vj的前一点。 Dijkstra算法步 骤： 第二步：考虑满足条件 的所有点； vi具有P 标号;vj具有T 标号; 修改vj的T标号为 ， 并将结果仍记为T(vj) 第一步：始点标上固定标号 ,其余各 点标临时性标号 T(vj)=, j1; 第三步：若网络图中已无T标号点，停止计算。 否则, 令 ，s为T标号点集, 然后将 的T 标号改成P 标号 ，转入第二步。 v1,6 图上标号法 v5 v2 2 3 4 6 4 v3 v1 v4 12 10 6 1 2 10 v8 v9 v7 2 3 6 3 v6 0,0 M, M, v1,3 M, M, M, v1,1v1,1 永久标号永久标号 临时标号 v1出发到v8去，使总费用最小的旅行路线 v1,6 图上标号法 v5 v2 2 3 4 6 4 v3 v1 v4 12 10 6 1 2 10 v8 v9 v7 2 3 6 3 v6 0,0 M, M, v1,3 M, M, M, 0,0 v1,1 v4,11 v1,3 永久标号 临时标号 v1出发到v8去，使总费用最小的旅行路线 v5 v2 2 3 4 6 4 v3 v1 v4 12 10 6 1 2 10 v8 v9 v7 2 3 6 3 v6 0,0 M, v1,1 M, M, M, 1,3 图上标号法 v4,11 v1,3 v1,6v3,5v3,5 永久标号 临时标号 v1出发到v8去，使总费用最小的旅行路线 v5 v2 2 3 4 6 4 v3 v1 v4 12 10 6 1 2 10 v8 v9 v7 2 3 6 3 v6 0,0 M, v4,11 v1,1 M, M, M, v1,3 图上标号法 v3,5 v2, 6v2, 6 永久标号 临时标号 v1出发到v8去，使总费用最小的旅行路线 v5 v2 2 3 4 6 4 v3 v1 v4 12 10 6 1 2 10 v8 v9 v7 2 3 6 3 v6 0,0 M, v4,11 v1,1 M, M, v1,3 v5,12 v5,9v5,9 图上标号法 v3,5 v2, 6 永久标号 临时标号 v5,10 v1出发到v8去，使总费用最小的旅行路线 v5 v2 2 3 4 6 4 v3 v1 v4 12 10 6 1 2 10 v8 v9 v7 2 3 6 3 v6 0,0 v5,10 v1,1 M, v5, 12 v1,3 v5,9 v5, 12 v3,5 v2, 6 图上标号法 永久标号 临时标号 v5,10 v1出发到v8去，使总费用最小的旅行路线 v5 v2 2 3 4 6 4 v3 v1 v4 12 10 6 1 2 10 v8 v9 v7 2 3 6 3 v6 0,0 v5,10 v1,1 M, v1,3 v5, 12 v3,5 v2, 6 图上标号法 v5,9 永久标号 临时标号 标号结束 反向追踪 v1出发到v8去，使总费用最小的旅行路线 Dijkstra算法步 骤： 第二步：考虑满足条件 的所有点； vi具有P 标号;vj具有T 标号; 修改vj的T标号为 ， 并将结果仍记为T(vj) 第一步：始点标上固定标号 ,其余各 点标临时性标号 T(vj)=, j1; 第三步：若网络图中已无T标号点，停止计算。 否则, 令 ，s为T标号点集, 然后将 的T 标号改成P 标号 ，转入第二步。 第51页 例 求如下交通网络中v1 到各点间最短路路长。 Dijkstra算法（标号法）算法（标号法）算例 3 10 2 5 v4 v1v2 v5 v3 1 22 6 2 4 4 8 混合图 第52页 5 7 2 7 4 6 1 2 6 3 2 0 2 6 5 7 7 10 v3 v1 v2 v4 v5 v6 v7 练习：求如下无向网络中v1到v7的最短链 Dijkstra算法求最短链 第53页 无向网络: 负权弧时。 wij vivj wij wij vjvi无向网络中，最短路最短链。 多个点对之间最短路？ v1v2 v3 1 2 -3 Dijkstra算法失效 Dijkstra算法注意的问题 逐步逼近算法 路矩阵算法 第54页 最短路问题求解方法 Dijkstra算法 逐步逼近算法 路矩阵算法 第55页 逐次逼近算法思想 表示点v1与vj之间最多插入k个转接点的最短路 第56页 用于计算指定点v1到其余各点的最短路 j=1,2,n. k=1,2,tn. 2.计算 逐次逼近算法基本步骤 j=1,2,n. 1.令 其元素既是v1到vj的最短路长。 3.当出现 时， 基本表 第57页 例 计算从点v1到所有其它顶点的最短路 解：初始条件为 以后按照公式 进行迭代。 直到得到 ，迭代停止。 v1 v2 v3 v4 v6 v5 v8 v7 2 -3 5 4 6 7 -2 4 -3 3 4 2 -1 第58页 v1 v2 v3 v4 v5 v6 v7 v8 v8v7v6v5v4v3v2v1 Wij v1 v2 v3 v4 v6 v5 v8 v7 2 -3 5 4 6 7 -2 4 -3 3 4 2 -1 4 0 0 -1 6 0 2 4 0 -3 3 -3 0 7 5 -2 0 4 2 0 0 利用下 标追踪 路径 到 从 例2：求 v1到各 点最短 路 第59页 逐次逼近算法思想 该公式表明，P(1)1j中的第j个分量等于P(0)1j的分量与 基 本表中第j列相应元素路长的最小值，它相当于在点v1 与vj 之间插入一个转接点（v1,v2,vn中的任一个，含点v1与vj）后所 有可能路中的最短路的路长；每迭代一次，就相当于 增加一个转接点，而P(k)1j中的每一个分量则随着k的增 加呈不增的趋势，直到出现稳定。 表示点v1与vj之间最多插入k个转接点的最短路 第60页 最短路问题求解方法 Dijkstra算法 逐步逼近算法 路矩阵算法 第61页 已知有7个村子，相互间道路的距离如下图示。拟合建一所 小学，已知A处有小学生30人，B处40人，C处25人，D处20人 ，E处50人，F处60人， G处60人,问小学应建在哪一个村子 ，使学生上学最方便（原则所有人走的总路程最短；尽 可能公平。）。 最短路问题算例1(选址问题) A G F E C B 5 2 2 7 4 7 1 6 3 D 2 6 A G F E C B 5 2 2 7 4 7 1 6 3 D 2 6 得到权矩阵为 得到权矩阵为 第64页 得到权矩阵为 A处30人， B处40人， C处25人， D处20人， E处50人，