运筹学（下篇）课件 第9-12章 图与网络-存储论

运筹学交通运输专业规划教材17十一月2025第2页下篇

本篇包含图与网络、统筹方法、排队论、存储论四个方面的内容。在图与网络中，首先给出了图的相关概念及其相关知识，在此基础上，给出了网络的概念以及相关知识。针对赋有权的网络，介绍了此类网络的三个应用问题，即最短路径问题、最小生成树问题、中国邮路问题；针对赋有容量、流量的网络，介绍了网络流的相关知识，然后重点介绍了此类网络的最大流问题及其算法；针对赋有容量、流量和权的网络，介绍了此类网络的最小费用流问题及其算法、最小费用最大流问题及其算法。最后为了扩展运用思路，介绍了复杂问题的网络应用，主要包括有条件限制的网络极值应用、有条件要求的网络流应用、网络的扩展应用问题。17十一月2025第3页下篇

在统筹方法中，首先给出了统筹图的概念以及统筹图的绘制规则，同时介绍了统筹图的关键路线问题，在此基础上介绍了确定关键路线的方法即时间参数法；针对工程费用，介绍了如何制定最少工程费方案问题；另外，针对非确定型统筹问题也作了一定的介绍。在排队论中，首先介绍了排队论的组成、特征以及排队模型的表示方法，通过对随机过程基础知识的介绍，给出了几个主要的马尔可夫排队模型及爱尔朗排队模型；另外，给出了关于定长分布和一般分布的两个排队模型。最后初步介绍了排队系统的最优决策问题。在存储论中，首先给出了存储论的基本概念，针对确定型存储问题，分别介绍了简单经济订货存储模型、经济生产批量存储模型、具有附加条件的存储模型中几个比较常见的确定型存储模型。另外，针对随机型存储问题，基于随机变量的离散性和连续性，介绍了几个比较常见的随机型存储模型。17十一月2025第4页下篇

1.图论与网络3.排队论4.存储论2.统筹方法（3）运输网络问题随机服务系统（随机过程）（1）基本知识（2）常见模型*排队最优化确定性存储模型随机存储模型（1）图的基本概念（2）网络规划问题确定型统筹问题：（1）统筹图概念、规则（2）关键路线（3）时间参数及其计算主要内容17十一月2025第5页第9章图与网络

在日常生活和工作中，经常会遇到各种各样的图或网络，如一个国家或地区的地图、国家铁路运输网、城市交通网、工程图、电信公司铺设的光纤网、自来水管道网等等。如果对某项工程的有关分析、决策等只是在实体上进行，那将会非常困难，这就需要把现实中的实体抽象成一种既简单而且又可以量化的图形。如何将现实中的实体抽象成可以量化的图或网络、如何对图或网络进行设计以及如何对图或网络进行分析等就是应用比较广泛的一个数学分支——图论。本章所介绍的图及网络是图论的有关知识，它的理论和方法在许多领域得到广泛的应用。17十一月2025第6页第9章图与网络

图及网络对实际问题描述具有直观性，可以将一些复杂的问题用图或网络的形式刻画出来，所以前面章节介绍的一般线性规划问题、运输问题、整数规划以及动态规划等有时可以用图论或网络的方法来解决。图论内容十分丰富，涉及面也比较广。在图基础上产生的网络规划也是数学规划理论的重要分支，网络规划是寻求系统最优的决策，即对网络模型寻求最优解。本章介绍的图与网络的理论和算法，是实际生活、生产和科研工作中经常用到的。首先学习一些有关图的相关知识以及网络的基本概念，在此基础上，主要学习网络图的应用问题，即研究网络规划问题。主要包括：最短路问题最小生成树问题中国邮路问题最大流问题最小费用流问题最小费用最大流问题17十一月2025第7页第9章图与网络

数学分支，可以解决线性规划等问题图的基本概念链、路、路径、回路、连通性等图图的矩阵表示图的相关运算

树及生成树有向图无向图关联矩阵邻接矩阵§9.1图的相关知识17十一月2025第8页第9章图与网络

§9.1.1图的基本概念

引例1:格尼斯堡七桥问题一个人能否从某地点出发，一次把七座桥不重复的都走过一遍，最后又回到原地？CADBCADBAB17十一月2025第9页第9章图与网络

引例2:

某大学创新协会共有7名同学，这7名同学中有的已经认识，有的还不认识，为了明确表明这7名同学之间的认识关系，现在用下图描述，其中用v1、v2、v3、v4、v5、v6、v7分别表示七名同学，用边表示他们是否认识v2v6v5v4v7v1v3例如，通过图可知：v1和v2之间的边就表示这两个点代表的两名同学是认识的，而v3和v4之间没有边，则说明这两个点代表的同学是不认识的。17十一月2025第10页第9章图与网络

引例3:假设下图是我国某地区几座城市之间的高速公路交通示意图，它反映了这几座城市之间高速公路的连接情况，其中点代表城市，点与点之间的边代表两座城市之间的高速公路。v2v3v4v5v1由以上三个例子可以看出，一般的图都具有两个要素，即点和边。把现实问题抽象为图的方法是，用点表示现实中的对象。用边表示对象和对象之间的关系，若对象和对象之间有关系，就用边把表示对象的点连接起来，直观的描述如右图所示。关系对象对象17十一月2025第11页第9章图与网络

自然语言的描述就是：图是由表示具体事物的对象（顶点）集合和表示事物之间的关系（边）集合组成。例如针对铁路网，边表示区段，顶点表示区段间的车站；针对城市道路网，边表示道路，顶点表示交叉口。如果用G表示图，用vi表示点，用V表示所有点的集合，用ei表示边，用E表示所有边的集合，则图的数学语言描述就是G=(V,E)，其中V=(v1,v2,…,vn)，E=(e1,e2,…,em)。另外图G的顶点集合与边集合也可分别用V(G)和E(G)表示。根据边有无方向，将图分为无向图、有向图和混合图，所有边都是无向边的图称为无向图；所有边都是有向边的图称为有向图；既有有向边又有无向边的图一般称为混合图。鉴于混合图的复杂现象，本教材不考虑混合图的相关问题。17十一月2025第12页第9章图与网络

无向图定义：存在图G=(V,E)，其中V是一个有n个顶点的非空集合，即V=(v1,v2,,…,vn)，E是一个有m条边的非空集合，即E=(e1,e2,…,em)，若E中任意一条边e是V的无序元素对(vi,vj)，其中i≠j，即可以有(vi,vj)=(vj,vi)，则称图G为无向图，见右图。v1v2v3v4v5如果把无向边用元素对表示，那么边(vi,vj)和边(vj,vi)是同一条边，vi和vj称为该无向边的端点，其中无向边与端点（顶点）vi和vj相关联，顶点vi和vj相邻，如上图中的边（v2,v4）和(v4,v2)属于同一条边，顶点v2和v4为该无向边的端点。17十一月2025第13页第9章图与网络

有向图定义：存在图G=(V,E)，其中V是一个有n个顶点的非空集合，即V=(v1,v2,…,vn)，E是一个有m条边的非空集合，即E=(e1,e2,…,em)，若E中任意一条边e是V的有序元素对(vi,vj)

，其中i≠j，即(vi,vj)≠(vj,vi)，称图G为有向图，见右图v1v2v3v4v5如果把有向边用元素对表示，那么边(vi,vj)和边(vj,vi)就不是同一条边，针对边(vi,vj)来说，顶点vi称为该有向边的起点，顶点vj称为该有向边的终点；但针对边(vj,vi)来说，顶点vj为该有向边的起点，顶点vi为该有向边的终点，如上图中有向边(v2,v4)和(v4,v2)就不是同一条边，顶点v2和v4为边(v2,v4)的起点和终点，但为边(v4,v2)的终点和起点。17十一月2025第14页第9章图与网络

§9.1.2图的相关术语

图既然分为无向图和有向图，所以将分别介绍无向图和有向图的有关术语，需要注意的是，针对无向图和有向图，尽管有一些术语的名称和表述相同，但要注意本质上会有一些差别。一无向图相关术语

平行边：无向图G中有相同端点的边称为平行边，如无向图

v2和v4中间的两条边简单图：如果无向图G中无平行边，图G也称为简单图，如右图即为简单图v2v3v4v5v1v1v2v3v4v517十一月2025第15页完备图：在无向图G中，若任意两个端点之间有且仅有一条边，图G也称为完备图。如下左图即为完备图：v1v2v3v4链：无向图G中，两个端点之间的连接路径称为链，如上右图中，v1和v5之间的连接路径v1v2v4v3v5即为链；一条链的起始端点和终止端点不为同一个端点的链称为开链，否则称为闭链，在上右图中，链v1v2v4v3为开链，链v1v2v4v3v1为闭链v1v2v3v4v5第9章图与网络

17十一月2025第16页初等链：在无向图G中，如果一条链中没有重复的顶点，则此链称

为初等链。v1v2v3v4v5如在下面两个相同的图中，链v1v3v4v2v3v5不是初等链，因为有重复的顶点v3，而链v1v2v4v3是初等链。v1v2v3v4v5第9章图与网络

17十一月2025第17页路：针对无向图G的一条链，若链中的每个点都不相同，则称这条链为连接链的起点和终点的路，如下图中链v1v2v4v3v5也称为路。回路：在一个无向图的闭链中，如果除了起始端点和终止端点相同外，没有相同的顶点和相同的边，则此闭链也称为回路。如上图中，闭链v1v2v4v3v1是回路，而闭链v1v2v4v3v2v1就不是回路，因为有相同的顶点v2和相同的边(v1,v2)v1v2v3v4v5v1v2v3v4v5第9章图与网络

17十一月2025第18页连通图：若无向图G中任意两点都能连通，则称无向图G为连通图，否则称为分割图。连通图中不存在任何孤立的顶点，即一个图中任意两点之间至少存在一条链。同构图：把结构相同一样，顶点的标识、位置及连接线的长短曲直可能不同的两个的图互称为同构图，如下图互为同构图。v1v2v3v4v1v4v2v3另外，假设Q为连通的无向图G的一条链，若图G中每一条边在链Q中恰好出现一次，则称链Q为欧拉链；若欧拉链是闭链，则该欧拉链也称为欧拉环游；若连通的无向图G中含有一条欧拉环游，则把图G也称为欧拉图。第9章图与网络

17十一月2025第19页第9章图与网络

二有向图相关术语

平行边：在有向图G中，起点和终点都相同的边称为平行边，如下左图中，顶点v2和v4之间的两条边即为平行边。v1v2v3v4v5简单图：若有向图G中无平行边，图G也称为简单图。完备图：若有向图G中，任意两个顶点之间恰好有两条非平行的有向边，则图G称为完备图，如上右图即为完备图。v1v4v2v317十一月2025第20页基本图：去掉有向图G中所有有向边的方向，就能得到一个无向图G*，此无向图G*称为有向图G的基本图。同构图：若有向图之间的顶点和边相互都能一一对应，则这些图互为同构图。初等链：有向图G的基本图G*中的初等链也称为有向图G的初等链。路：针对有向图G的一条链，若链中每个点都不相同，则称这条链为连接该链起点和终点的路，如右图中链v1v3v4v2称为路。回路：起点和终点重合的路称为回路，如右图路v1v3v4v2v1称为回路第9章图与网络

v1v2v3v4v517十一月2025第21页第9章图与网络

§9.1.3图的相关运算设图G=(V,E)、G1=(V1,E1)，若V1

V，E1

E，则称G1为G的子图，记为G1

G；当G1

G且G1≠G时，称G1为G的真子图，记为G1

G；当G1

G并且V1=V时，称G1为G的生成子图。如下中图就是下左图的真子图，下右图就是下左图的生成子图。v1v2v3v4v1v2v3v1v2v3v4对图通常可以进行并、交、差的相关运算17十一月2025第22页设图G1=(V1,E1)、图G2=(V2,E2)和图G=(V,E)，下面给出相关运算：并运算：针对G1∪G2=G，有V(G)=V(G1∪G2)=V1∪V2，E(G)=E(G1∪G2)=E1∪E2。如下图体现了图的并运算v1v2v3图G1v2v3v4图G2v1v2v3v4图G1∪G2第9章图与网络

17十一月2025第23页交运算：针对G1∩G2=G，则有E(G)=E(G1∩G2)=E1∩E2，而V(G)=V(G1∩G2)则为图G1和图G2的E1∩E2中边的全体端点。如下图体现了图的交运算。v1v2v3v4图G1v1v2v3图G1∩G2图G2v1v2v3v4第9章图与网络

17十一月2025第24页差运算：针对G1-G2=G，则有E(G)=E(G1-G2)=E1-E2，而V(G)=V(G1-G2)则为图G1和图G2的E1-E2中边的全体端点，如下图体现了图的差运算。v2v3v4图G2图G1v1v2v3v4v1v2v3图G1-G2第9章图与网络

17十一月2025第25页第9章图与网络

§9.1.4树及生成树

无回路并且能连通的无向图G称为树，记为T=(V,E)，树中的边称为枝；若图T是无向图G的生成子图，并且T又是树，则称图T是无向图G的生成树。树T满足V(T)=V(G)，E(T)

E(G)，也就是说生成树是把原图上的顶点以最少的边而连接起来的树。由于边的取法不同，同一个图可以有很多生成树，如下中图和下右图就是下左图的部分生成树

17十一月2025第26页第9章图与网络

针对一个图如何寻找生成树有一定的方法，这里介绍两种方法即破圈法和避圈法。寻找图的生成树方法如下：（1）破圈法（Kruskal算法，也称去边法）破圈法就是在图G中任取一个回路，从所取的回路中去掉一条边，如此反复进行，直到图G中无回路为止，余下的子图即为原图G的生成树。（2）避圈法（也称着色法或重绘法）在图G中任取一边ei，找不与边ei构成回路的边ej，再找不与边ei和边ej构成回路的边ek，如此反复进行，直到不能进行为止。17十一月2025第27页第9章图与网络

§9.1.5图的矩阵表示图可以用几何的形式存储到计算机系统中，但计算机针对图的运用、决策等需要时，就面临着数据计算的问题，这就涉及到数据和图互相转换的处理方法。即把图转换为数据的形式，然后存储到计算机系统中，反之，可以把计算机系统中的数据转换成几何形式的图形，而矩阵就是数据和图互换时比较可用的方式。无论无向图还是有向图，都可以用关联矩阵或邻接矩阵的形式表示出来。有了关联矩阵和邻接矩阵，就可以把图以数据的形式存储在计算机系统中，反过来，可以根据计算机系统中的数据矩阵，按照一定的方法把图绘制出来。本节分别介绍无向图和有向图的关联矩阵和邻接矩阵的表示方法。17十一月2025第28页第9章图与网络

一无向图的矩阵表示1无向图的关联矩阵

e1…ej

…em矩阵数值aij规则：aij=0，顶点vi与边eij不关联1，顶点vi与边eij关联17十一月2025第29页示例：写出右图的关联矩阵v1v2v3v4v5e1e2e3e4e5e6e7特点：（1）第i行中1的个数就是与顶点vi相连接的边的数量。（2）第j列中1的个数恒为2，因为每条边只有2个端点。第9章图与网络

e1

e2

e3

e4

e5

e6

e717十一月2025第30页2无向图的邻接矩阵v1…

vj

…

vn矩阵数值aij规则：aij表示顶点vi和vj之间边的数量邻接矩阵刻画了无向图G的顶点之间边的连接数量情况。第9章图与网络

17十一月2025第31页示例：写出右图的邻接矩阵v1v2v3v4v5e1e2e3e4e5e6e7v1

v2

v3

v4

v5

特点：（1）对角线上的元素均为0，同时邻接矩阵也是对称矩阵。（2）每行或每列上的数据之和就是对应顶点上边的数量。（3）一般来说邻接矩阵比关联矩阵小。第9章图与网络

e1

e2

e3

e4

e5

e6

e7e8

17十一月2025第32页第9章图与网络

一有向图的矩阵表示1有向图的关联矩阵与无向图的关联矩阵形式一样，但数值aij规则为：e5v1v2v3v4v5e1e2e3e4e7e8e6特点：（1）第i行中1的个数就是以顶点vi为起点的边的数量，-1的

个数就是以顶点vi为终点的边的数量。（2）第j列中的元素之和恒为0。17十一月2025第33页2有向图的邻接矩阵有向图的邻接矩阵与无向图邻接矩阵唯一不同的是：aij的值是以顶点vi为起点，以顶点vj为终点的边的数量e5v1v2v3v4v5e1e2e3e4e7e8e6v1

v2

v3

v4

v5

特点：（1）对角线上的元素均为0。（2）第i行中的元素之和就是以顶点vi为起点的有向边的数量。（3）第j列中的元素之和就是以顶点vj为终点的有向边的数量。（4）同样邻接矩阵比关联矩阵小。第9章图与网络

17十一月2025第34页第9章图与网络

§9.2网络的相关知识

通过图G=(V,E)的概念可知，图是由点和边组成，点表示现实世界中的对象，边表示对象之间的关系，但在图的定义中，对所谓的关系没有进行量化，即对象之间的关系是何种关系、关系的程度又如何等等都没有系统的涉及。为了更深入地利用图解决现实中的问题，就需要对图中的边甚至图中的点进行量化，也就是说，只要现实中的问题具有可描述的对象，而且这些对象之间有着一种关系，那么对这种关系就可以进行量化，即把现实中的对象和关系描绘成图以后，在图的基础上，把图中的边或点赋上表示一定意义的数量指标，这个数量指标称为权，这样就可以把现实的问题通过图转化成网络。17十一月2025第35页第9章图与网络

对于网络，人们在现实生活中并不陌生，比如常说的交通网、公交网、水网、管网、电网、信息网等等，在理论上所谓的网络即是赋有权的图，有时人们不加区别地统称图、网络、网络图或赋权图。网络和图最大的区别在于网络具有表示权的数值。针对不同的现实问题，权就有不同的意义，权可以表示现实中的距离、费用、时间、成本、交通流量、水流量、电流量、公交乘客流、运输物资流等等。研究网络的目的就是如何利用网络解决现实的问题，根据赋权的不同，网络就有不同的应用。在后面的网络理论中，主要讲解网络极值问题和网络流问题，其中网络极值问题主要包括最短路径问题、最小生成树问题以及中国邮路问题等；网络流问题主要包括最大流问题、最小费用流问题以及最小费用最大流问题。另外，为了解决现实中的复杂问题，最后针对性地介绍一些网络的灵活运用问题。17十一月2025第36页第9章图与网络

网络极值网络理论网络流问题网络的灵活运用问题最短路径问题最小生成树问题中国邮路问题最大流问题最小费用流问题最小费用最大流问题17十一月2025第37页第9章图与网络

§9.3网络极值问题在实际的工作或生活中，往往会遇到需要解决网络极值问题，如货物的布局、公交网站点规划、城市自来水网铺设、安全巡游等一系列的网络极值问题，为了利用网络把这些问题更好的刻画出来，下面给出网络极值的数学定义。给定图G=(V,E)，其中V=(v1,v2,…,vn)，E=(e1,e2,…,em)，现在把图G的每条边都赋予一个非负的实数，即wi=w(ei)或wij=w(vi,vj)，这个非负的实数称为权。在图G的基础上，就有了关于极值的网络定义G=(V,E,W)，其中W=(w1,w2,…,wm)，根据此定义，具有极值的网络图中的边就有了如下的形式：vivjwij无向网络中的边vivjwij有向网络中的边17十一月2025第38页第9章图与网络

下面的图分别为无向网络和有向网络。4v1v2v3v4v5342523v1v2v3v4v5532314有了关于极值的网络定义，就可以研究和解决现实中的最短路径问题、最长路径问题、最小生成树问题及中国邮路问题等。17十一月2025第39页第9章图与网络§9.3.1最短路径问题实际问题中，经常会遇到运输管理、管道铺设、交通网优化、物流调配、费用（成本）核算、工程进度等问题，这就需要解决出行距离最小、花费成本最低、距离最短、最优路径等一系列网络图寻优问题，对这些类似问题可以用“最短路径”来表述，有时简称为最短路。最短路问题是图论的核心问题之一，也是网络规划的一个基本问题，无向网络和有向网络都有对应的最短路径问题。所谓最短路就是从网络中一点寻求到其它点的最短的路，具体什么是最短路，简言之最短路就是从网络中某一点到另外一点的所有路中，所有边的权之和最小的路，把路中所有边的权代数和称为路长。如果用P来表示网络中从点vs到点vt的一条路，用W(P)来表示该路的路长，若P*也为网络中从点vs到点vt的路，并且满足W(P*)=min{W(P)|P为网络中从点vs到点vt的路}，则P*即是点vs到点vt路的最短路。17十一月2025第40页第9章图与网络

为了对最短路有更具体和更形象的认识，下面给出一个例题。例假设下图为规划论证的某一城市区域内可以开通公交的公交线网，顶点表示停靠站，边表示道路，边旁数据表示道路长度，某公交公司准备在起始站v1和终点站v8之间开通一条距离最短的公交线路，现在需要确定这条公交线路的走向。4v1v2v3v4v515v7v6v83516273722117十一月2025第41页第9章图与网络

针对此问题最容易想到的求解思路就是，设法把从v1到v8的所有路都找出来，然后再计算每条路中关于边的权的代数和即路长，最后取路长最小的路作为所求的最短路，即有如下过程：路v1→v2→v5→v6→v8，其长度为1+5+7+1=14；路v1→v2→v4→v6→v8，其长度为1+3+3+1=8；路v1→v2→v5→v4→v6→v8，其长度为1+5+6+3+1=16；……………………路v1→v3→v7→v8，其长度为4+2+2=8；路v1→v3→v7→v6→v8，其长度为4+2+2+1=9。通过比较可以知道最短路为v1→v2→v4→v6→v8和v1→v3→v7→v8，路长为8。即可以按照v1→v2→v4→v6→v8或v1→v3→v7→v8的走向开通一条距离最短的公交线路。17十一月2025第42页第9章图与网络

上面例子的求解过程采用的是全枚举法，这种方法虽然很明了，但是过程繁琐，而且容易出错，尤其是对一些稍微复杂的网络，这样的算法几乎很难实现，因为点或边很多的网络，网络中的路就会很多，而且在现实中遇到的网路几乎都是相对复杂的网路，所以就需要有更方便、简洁的算法求最短路问题。最短路的求解算法很多，主要有Dijkstra算法、Bellman-Ford算法以及SPFA算法等等，这些算法是许多更深层算法的基础。在目前使用比较普遍而且得到公认的经典算法就是E.W.Dijkstra在1959年提出的最短路求解算法，简称为Dijkstra算法。这个算法另外一个特点就是，不仅能求出某点到另外一点的最短路，也能求出某点到网络中其它各个点的最短路。下面对Dijkstra算法的相关内容进行介绍。一Dijkstra算法思想在网络图G中，假设从顶点v1到顶点vn的最短路径P为v1…vi…vn，那么从v1沿着路径P到vi的路径P1也是v1到vi的最短路，也就是说，P不仅是起点v1到终点vn的最短路，而且由v1到路径P上任意一个中间点vi的最短路P1也在路径P上。

17十一月2025第43页第9章图与网络

设从vi沿着路径P到vn的路径为P2，那么就有W(P)=W(P1)+W(P2)；利用反证法，反设从v1到vi的最短路不是路径P1，而是另外一条路径P'，即有W(P')＜W(P1)，这也就有W(P')+W(P2)＜W(P1)+W(P2)，此时出现了W(P′)+W(P2)＜W(P)，这就说明从v1到vn的最短路不是路径P，而是P′与P2组成的路径，这就与从v1到vn的最短路径是P的前提相矛盾。由以上性质可以想到，为了求由v1到vn的最短路径，可以先求出v1到网络中间点的最短路，然后再逐步扩展到终点vn，由此，Dijkstra算法的思想如下：路径P路径P′vnv1vi路径P1路径P2论证：17十一月2025第44页第9章图与网络

在最短路的计算过程中，为了将已经求出最短路的点与尚未求的点分开，为此针对顶点给出两个子集合S和T，已经求出最短路的点置于集合S中，其它点置于集合T中。开始时把起点v1置于集合S中，把其它点置于集合T中，随着最短路计算过程的推移，集合S中的点逐渐增多，集合T中的点逐渐减少，当终点vn也被纳入到集合S中时，计算结束。为了便于计算和区分各个顶点是否已进入集合S中，需要对已求出最短路的点vj赋以标号，这个标号由两部分组成，记为(d(v1,vj),vi），其中d(v1,vj)是从起点v1到vj的最短路的路长，vi是起点v1到vj的最短路中vj的前一个顶点。因为Dijkstra算法需要标号，所以也称为标号法，又因为标号中包含两部分，所以也称为双标号法。二Dijkstra算法步骤给定一个网络G=(V,E)，这里用wij表示网络中边(vi,vj)的权，v1是网络的起点，vn是终点，vi、vj等是网络的中间节点，其中i，j=2,3,…,n-1且i≠j，设子集合S和T，S=

，T=V={v1,…,vn}。17十一月2025第45页第9章图与网络

再设L(v1,vi)表示起点v1到点vi的当前最短路的路长，可以把L(v1,vi)简写为L(vi)；同样，L(v1,vj)表示起点v1到点vj的当前最短路的路长，也把L(v1,vj)简写为L(vj)；L(vi)+wij是从起点v1出发，沿着起点v1到点vi的最短路，经由vi后到点vj的路长。那么L(vj)=min{L(vi)+wij

；L(vj)}就是从起点v1到点vj的两条路径中，选择最短的一条作为起点v1到点vj新的最短路的路长。v1到vj当前最短路，路长L(vj)L(vj)=min{L(vi)+wij；L(vj)}表示从v1到vj的两条路径中选择最短的一条作为v1到vj的新的最短路。v1到vi当前最短路，路长L(vi)wijviv1vj17十一月2025第46页第9章图与网络

由Dijkstra算法思想及前面的相关界定，求v1到vn最短路的Dijkstra算法步骤如下：第一步：设L(v1)=0，L(vi)=+∞，其中i=2,…,n。在网络图中，把起点v1赋以标号（L(v1),v1），即（0,v1），其余各点均标为（+∞,v1）。第二步：检查起点v1，即将网络中v1的标号变为(0*,v1），表示v1已被检查，同时设集合S={v1}，T={v2,…,vn}。

第四步：计算L(vi)*=min{L(vi),其中vi

T}，将L(vi)*对应点vi的第一个标号L(vi)标上*，即变为L(vi)*，表示vi已被检查，同时设集合S={v1,vi}，此时vi

T。

第三步：针对其它点vi，若v1与vi没有直接连线，vi的标号就保持不变；若v1与vi有直接连线，则点vi的标号就变为(L(vi),v1)，其中：

L(vi)=min{L(v1)+W1i；L(vi)}=min{0+W1i；+∞}=W1i17十一月2025第47页第9章图与网络

第六步：计算L(vj)*=min{L(vj),其中vj

T}，将L(vj)*对应点vj的第一个标号L(vj)标上*，即变为L(vj)*，表示vj已被检查，同时设集合S={v1,vi,vj}，而vj

T。第七步：返回第五步，直到所有的点都被检查，而且终点vn进入到集合S中为止。第八步：在网络中，从终点vn的第二个标号开始反向追踪，从而找出最短路径；同时从终点vn的第一个标号可以读出起点v1到终点vn最短路的路长。另外，从各个点的第一个标号也可以读出从起点v1到该点的最短路的路长。第五步：再依次求vj，若vi与vj没有直接连线，vj的标号就保持不变；若vi与vj有直接连线，则计算L(vj)=min{L(vi)+wij；L(vj)}。若L(vj)值来源L(vi)+wij，则把vj的标号修改为(L(vi)+wij,vi），否则点vj的标号保持不变。17十一月2025第48页第9章图与网络

三最短路算法应用示例用dijkstra算法求下面网络图中点v1到点v8的最短路4v1v2v3v4v515v7v6v835162737221具体解题步骤如下：

第一步：设L(v1)=0,L(vi)=+∞,其中i=2,…,8.在网络中,把起点v1赋以标号(L(v1),v1),即(0,v1),其余各点均标为(+∞,v1),检查起点v1,并将网络中v1的标号变为(0*,v1),同时设集合S={v1},T={v2,…,v8},如下图：17十一月2025第49页第9章图与网络

710*,v14v1v2v3v4v55v7v6v83516273221+∞,v1+∞,v1+∞,v1+∞,v1+∞,v1+∞,v1+∞,v1第一步计算结果：L(vi)kv1v2v3v4v5v6v7v81

0*+∞+∞+∞+∞+∞+∞+∞vi17十一月2025第50页第二步:v1与v2、v3有直接连线，则L(v2)=min{L(v1)+W12;L(v2)}=min{0+1;+∞}=1，点v2的标号变为(1,v1)。同理L(v3)=min{L(v1)+W13;L(v3)}=min{0+4;+∞}=4，点v3的标号就变为(4,v1），其余点的标号保持不变。再计算：L(vi)*=min{L(vi)}=min{L(v2),L(v3),L(v4),…,L(v8)}=min{1,4,+∞,…,+∞}=1=L(v2),将网络中v2的标号变为(1*,v1),同时设集合S={v1,v2},此时v2

T，如下图70*,v14v1v2v3v4v515v7v6v835162732211*,v1+∞,v14,v1+∞,v1+∞,v1+∞,v1+∞,v1第9章图与网络

17十一月2025第51页第二步计算结果：L(vi)vikv1v2v3v4v5v6v7v810*+∞+∞+∞+∞+∞+∞+∞2

11*41+∞+∞+∞+∞+∞第三步：从v2开始继续检查，v2与v3、v4、v5有直接连线，L(v3)=min{L(v2)+W23;L(v3)}=min{1+5;4}=4,点v3的标号保持不变；L(v4)=min{L(v2)+W24;L(v4)}=min{1+3;+∞}=4,点v4的标号变为(4,v2);L(v5)=min{L(v2)+W25;L(v5)}=min{1+5;+∞}=6,点v5的标号变为(6,v2),其余点的标号保持不变。再计算：L(vi)*=min{L(vi)}=min{L(v3),L(v4),L(v5),…,L(v8)}=min{4,4,6,…,+∞}=4=L(v3)=L(v4)对最小值L(v3)和L(v4)可以任意取一个,这里取L(v3)作为最小值，将网络中v3的标号修改为（4*,v1）,同时设集合S={v1,v2,v3}，此时v3

T，第9章图与网络

17十一月2025第52页70*,v14v1v2v3v4v515v7v6v835162732211*,v16,v24*,v14,v2+∞,v1+∞,v1+∞,v1+∞+∞+∞6242

41*3+∞+∞+∞+∞+∞41

11*2+∞+∞+∞+∞+∞+∞+∞0*1v8v7v6v5v4v3v2v1L(vi)vik第三步计算结果：如下图所示。同时将上表格扩展为下表第9章图与网络

17十一月2025第53页第四步：从v3开始继续检查，v3与v7有直接连线，L(v7)=min{L(v3)+W37；L(v7)}=min{4+2；+∞}=6，点v7的标号变为（6,v3），其余点的标号保持不变。再计算：L(vi)*=min{L(vi)}=min{L(v4),L(v5),L(v6),L(v7),L(v8)}=min{4,6,+∞,6,+∞}=4=L(v4)将网络中v4标号改为(4*,v2），设集合S={v1,v2,v3,v4}，此时v4

T，70*,v14v1v2v3v4v515v7v6v835162732211*,v16,v24*,v14*,v26,v3+∞,v1+∞,v1第9章图与网络

17十一月2025第54页第四步计算结果：L(vi)vikv1v2v3v4v5v6v7v81

0*+∞+∞+∞+∞+∞+∞+∞2

11*41+∞+∞+∞+∞+∞3

41*4262+∞+∞+∞4

42*62+∞63+∞第五步：从v4开始继续检查,v4与v3、v6、v7有直接连线，L(v3)=min{L(v4)+W43;L(v3)}=min{4+1;4}=4,点v3的标号保持不变；L(v6)=min{L(v4)+W46;L(v6)}=min{4+3;+∞}=7,点v6的标号变为(7,v4);L(v7)=min{L(v4)+W47;L(v7)}=min{4+7;6}=6,点v7的标号保持不变,其余点的标号保持不变。再计算：L(vi)*=min{L(vi)}=min{L(v5),L(v6),L(v7),L(v8)}=min{6,7,6,+∞}=6=L(v5)=L(v7).这里取L(v7)作为最小值，就将网络中v7的标号修改为(6*,v3），同时设集合S={v1,v2,v3,v4,v7}，此时v7

T第9章图与网络

17十一月2025第55页70*,v14v1v2v3v4v515v7v6v835162732211*,v16,v24*,v14*,v26*,v37,v4+∞,v1第五步计算结果：L(vi)vikv1v2v3v4v5v6v7v81

0*+∞+∞+∞+∞+∞+∞+∞2

11*41+∞+∞+∞+∞+∞3

41*4262+∞+∞+∞4

42*62+∞63+∞56274

63*+∞第9章图与网络

17十一月2025第56页第六步：从v7开始继续检查，v7与v6、v8有直接连线，L(v6)=min{L(v7)+W76；L(v6)}=min{6+2；7}=7，点v6的标号保持不变；L(v8)=min{L(v7)+W78；L(v8)}=min{6+2；+∞}=8，点v8的标号变为(8,v7），再计算：L(vi)*=min{L(v5),L(v6),L(v8)}=min{6,7,8}=6=L(v5)将网络中v5的标号修改为(6*,v2），同时设集合S={v1,v2,v3,v4,v7,v5}，此时v5

T

0*,v14v1v2v3v4v515v7v6v8351627372211*,v1

6*,v24*,v14*,v26*,v37,v48,v7第9章图与网络

17十一月2025第57页L(vi)vikv1v2v3v4v5v6v7v81

0*+∞+∞+∞+∞+∞+∞+∞2

11*41+∞+∞+∞+∞+∞3

41*4262+∞+∞+∞4

42*62+∞63+∞56274

63*+∞6

62*7487第六步计算结果：第七步：再从v5开始继续检查，v5与v6有直接连线，L(v6)=min{L(v5)+W56；L(v6)}=min{6+7；7}=7，点v6的标号保持不变。再计算：L(vi)*=min{L(v6),L(v8)}=min{7,8}=7=L(v6)将网络中v6的标号变为(7*,v4），同时设集合S={v1,v2,v3,v4,v7,v5,v6}，此时v6

T

第9章图与网络

17十一月2025第58页0*,v14v1v2v3v4v515v7v6v8351627372211*,v1

6*,v24*,v14*,v26*,v37*,v48,v7L(vi)vikv1v2v3v4v5v6v7v81

0*+∞+∞+∞+∞+∞+∞+∞2

11*41+∞+∞+∞+∞+∞3

41*4262+∞+∞+∞4

42*62+∞63+∞56274

63*+∞6

62*74877

74*87第七步计算结果：第9章图与网络

17十一月2025第59页第八步：从v6开始继续检查,v6与v8有直接连线，L(v8)=min{L(v6)+W68;L(v8)}=min{7+1;8}=8。最小值8来自两处，点v8的标号应该为(8,v6)和(8,v7),点v8的标号写为(8,v6v7).再计算：L(vi)*=min{L(vi)}=min{L(v8)}=min{8}=8=L(v8)将网络中v8标号变为(8*,v6v7),同时设集合S={v1,v2,v3,v4,v7,v5,v6,v8},此时v8

T70*,v14v1v2v3v4v515v7v6v835162732211*,v1

6*,v24*,v14*,v26*,v37*,v48*,v6v7第9章图与网络

17十一月2025第60页第八步计算结果：L(vi)vikv1v2v3v4v5v6v7v810*+∞+∞+∞+∞+∞+∞+∞2

11*41+∞+∞+∞+∞+∞3

41*4262+∞+∞+∞4

42*62+∞63+∞56274

63*+∞6

62*74877

74*878

867*此时终点v8已经被标识和检查，算法结束。从终点v8的第一个标号可以读出起点v1到终点v8最短路的路长为8，同时从终点v8的第二个号开始反向追踪，找出最短路径为v1→v2→v4→v6→v8和v1→v3→v7→v8，此网络有两条最短路。第9章图与网络

17十一月2025第61页特别提示：（1）网络中的最短路不止一条时，要注意进行多点标号，如上例的第八步。另外，上例是利用dijkstra算法对有向网络进行寻找最短路，dijkstra算法对无向网络的使用原理一样。（2）dijkstra算法只适用于网络中所有边的权Wij≥0的情况，当网络中出现负权边的时候，dijkstra算法就不能保证得到正确的结果。（3）另外，同样也可以读出从起点v1到该网络中任意一点的最短路及路长。（4）针对含有负权边求最短路的算法很多，但因这类问题算法的复杂性较高，本教材不作介绍。第9章图与网络

17十一月2025第62页第9章图与网络

§9.3.2最小生成树问题在第9.1.4节中，介绍了基于图的树以及生成树问题，针对具有权的网络，常常需要寻找基于权之和最小的生成树，这就是最小生成树问题。具有一定的实用意义，如常常需要以最研究最小生成树问题短线路连接网络中若干个固定点，例如城市水网铺设、交通网规划、煤气管网建设等等，为了便于维护、管理等目的，这些都涉及到线网中总长度最短的问题。这些问题需要在线网中找出一棵最小生成树，类似的问题还有，如何设计总长度最小的公交网或公路网把若干城镇连接起来等等，也就是说，许多网络问题会派生出最小生成树问题，因此，最小生成树问题也是网络极值的基本问题之一。下面的示例就是在网络图中找出一棵最小生成树问题。17十一月2025第63页引例：图中表示10个居住小区间道路连接以及距离情况，问如何开通公交线路使公交车运行路程最短？对于给定的网络图，常常含有许多不同的树，如何找出具有某种最小性质的树？第9章图与网络

4563v1v2v3v4v5v7v6v8v9v104454335265178217十一月2025第64页给定无向网络图G=(V,E)，其中V=(v1,v2,…,vn)，E=(e1,e2,…,em)，针对边ei的实数权为w(ei)，令T是G的生成树，则生成树T的权之和为：第9章图与网络

一最小生成树的数学描述若T*也是G的生成树，且有W(T*)=min{W(T)|T是G的一个生成树}，则称T*是无向网络图G的最小生成树。二寻找最小生成树的方法在第9.1.4节中，已经介绍了针对图寻找生成树的两种方法，即破圈法和避圈法。针对具有权的网络图，寻找最小生成树的方法仍然是基于破圈法和避圈法的思路，但需要考虑权的大小问题。17十一月2025第65页第9章图与网络

下面给出网络中寻找最小生成树的破圈法和避圈法的思路（1）避圈法在连通的无向网络图G中，从所有边中选出一条权最小的边，并把它纳入树中，在G中余下的边中再选择一条权最小且与选进树中的边不构成回路的边，同样将其纳入树中，如此反复，直到找不出这样的边为止。（2）破圈法在连通的无向图G中，任取一个回路，将该回路中权最大的边去掉，如果回路中含有两条及两条以上权最大的边，则任取一条，再在余下的回路中重复这一步骤，直到图G中不含有回路为止。17十一月2025第66页“一个邮递员每次送信，从邮局出发，必须至少一次地走过他负责投递范围的每一条街道，完成投递任务后仍然回到邮局，问他如何选择一条投递路线，使他所走的路程最短？”，这个问题是我国管梅谷在1962年首先提出，所以称为中国邮路问题。3410v16v2v3v7v6v5v4v8v9例：邮递员需从v1出发，走遍每条街道递送邮件，最后再回到v1，他应选择什么路线才能使总的路程长度最短第9章图与网络

§9.3.3中国邮路问题17十一月2025第67页给定一个连通的无向网络图G=(V,E,W)，所有边(vi,vj)的权wij>0，现在要求每条边至少通过一次的闭链Q，使得总权最小。如果图G恰好是欧拉图，那么从邮局出发，恰好每边走一次可回到邮局，这时总权必定最小；如果图G不是欧拉图，则某些边必然要重复走，当然要求重复走过边的总长度最小。第一步：若网络图G是一个欧拉图，即没有奇阶点（奇阶点指与点连接的边的数量为奇数），则该图可以一笔画出全部的边而无重复，此时，邮递员的最优路线就是一个欧拉环游，其总的走行长度为全部边长之和，但一般而言，街道图并非欧拉图，那么可以采用以下办法消除奇阶点，从而将非欧拉图变为欧拉图：第9章图与网络

一中国邮路问题的数学描述二中国邮路问题的一个算法17十一月2025第68页（1）找出全部奇阶点(全部奇阶点的顶点个数一定是偶数个);（2）将2m个奇阶点构成m个奇阶点对，使每点都在一个点对中，找出每个点对中两个奇阶点之间一条链，对应于链上的每条边都添加一条长度和该边相等的边，经过添加边的两点间的街道，邮递员需要两次经过。第二步：解奇阶点匹配问题最优解的分枝定界算法。设au,v为奇阶点u至奇阶点v的最短路长度，将全部2m个奇阶点的最短路长度构成一个2m×2m的矩阵：第9章图与网络

17十一月2025第69页将A视为一个指派问题的费用矩阵，并令主对角线各元素等于∞，现在，对这个指派问题求解，最优解用2m个表中位置表示。如果最优解在表中是关于主对角线对称（称为对称解），则这个表右上角即为奇阶点匹配问题的最优解；如果指派问题最优解不是对称解，则解中必然存在由n个表位（n>2）构成的下标回路，如：(1,3）、(3,5）、(5,1），为了寻求对称解，这个回路必然打破，因此，可分别令表中这n个位置上的元素等于∞，将指派问题分枝成n个子问题，继续用指派问题的算法，计算出各子问题的目标值，做为该子问题以后分枝的目标下界，这样不断分枝下去，直至没有任何一个子问题需要再分枝，即可确定奇阶点匹配问题的最优解。任一子问题停止分枝的条件是：（1）该子问题的解为对称解；第9章图与网络

17十一月2025第70页（2）其目标下界大于等于某一具有对称解的子问题的目标值。计算步骤如下：1.找出全部奇阶点，用最短路算法计算全部奇阶点任一点对间的最短路长度。

2.将奇阶点最短路长度矩阵A视为指派问题的费用矩阵，构成一个指派问题，形成初始子问题矩阵后，将某些不可能进入奇阶点匹配问题最优解的表位排除掉：（1）如果点i至点j的最短路由三个以上奇阶点组成，那么令ai,j=∞，aj,i=∞；（2）检查所有三奇阶点最短路，设为i—j—k，如果其中间点j与任何其他奇阶点构成的最短路都包含一个端点i或k，则令它们在初始子问题表中的元素ai,k=∞，将该问题置入待分枝子问题集合B，令奇阶点匹配问题的候选最优解目标T=∞。第9章图与网络

17十一月2025第71页

3.如果B为空，则停止计算，候选最优解S即为最优解；如果B非空，则从B中取出一个子问题k，用指派问题算法解子问题k。其目标值为Tk，解为Sk（以分配的表位集合表示）。4.若Tk＞T则停止分枝，转第3步取另一子问题，否则转第5步。6.在Sk中找出一个点数为n的下标回路(i1,j1)、(i2,j2)、…、(in,jn），其中i2=j1,i3=j2…,in=jn-1，而且n>2，分别令子问题k的矩阵Ak中的，构成n个子问题，并置入待分枝子问题集合B，然后转第3步。第9章图与网络

5.若Sk关于主轴对称，停止分枝，令候选最优解等于子问题k的解，令S=Sk，T=Tk，然后转三取另一个子问题；若Sk为非对称解，转第六步。17十一月2025第72页求上面示例中的最短邮递路线解：图14有6个奇阶点，其对应的奇阶点之间的最短路矩阵如左下：

针对上述A矩阵，按照指派问题求解思路求对应的最优解，最优解矩阵如右上所示：

指派问题的解不对称,从而相对应的中国邮路问题的解不可行,解中存在如下下标环(1,4)、(4,5)、(5,1),现在分别将A矩阵中下标环中三个位置及其对称位置的数值置为∞,从而构造出以下三个子问题:第9章图与网络

17十一月2025第73页子问题1：将A矩阵中(1,4）和(4,1）处的元素置为∞，构造出如左下指派问题：最优解不对称，子问题1的解不可行，最优目标函数值为36。子问题1最优解矩阵

子问题2：将A矩阵中(4,5）和(5,4）处的元素置为∞，构造出如左下指派问题：子问题2最优解矩阵第9章图与网络

17十一月2025第74页最优解对称，子问题2可行，最优目标函数值为36，添加边方案：7-8、2-9、5-1，添加边总长18

子问题3：将A矩阵中(5,1）和(1,5）处的元素置为∞，构造出如左下指派问题：子问题3最优解矩阵

最优解对称，子问题3可行，最优目标函数值为36，添加边方案：5-6-7、8-9、2-9-10，添加边总长18。由停止分枝的条件，子问题都不再往下分枝，已得到此中国邮路问题的最优解，子问题2或子问题3都是该问题的最优解。第9章图与网络

17十一月2025第75页第9章图与网络

§9.4网络流问题在上一节中，把图中的边赋予权的数量指标后，研究了网络的极值问题，如果把图中的边赋予其它意义的数量指标，就可以产生网络流的问题。研究网络流的问题有一定的现实意义，例如交通系统中的车流、金融系统中的现金流、控制系统中的信息流、供水系统中的水流等等，针对这些系统，有时需要考虑在既定的网络中能通过网络的最大流量是多少，这就产生了网络的最大流问题；有时需要考虑在满足成本最低的前提下，使网络承载一定的流量，这就产生了网络的最小费用流问题；有时也需要考虑在满足成本最低的前提下，使网络通过的流量达到最大，这就产生了网络的最小费用最大流问题。这些问题可以说是线性规划问题，用线性规划的方法也可以解决，但依据现实问题抽象出来的网络模型具有特殊的结构，而且网络模型也具有直观性，所以基于网络模型可以设计出比单纯形法更为有效的的算法来解决这类问题。17十一月2025第76页第9章图与网络

§9.4.1网络流的相关知识在上一节中，把图中的边赋予权的数量指标后，研究了网络的极值问题，如果把图中的边赋予其它意义的数量指标，就可以产生网络流的问题。研究网络流的问题有一定的现实意义，例如交通系统中的车流、金融系统中的现金流、控制系统中的信息流、供水系统中的水流等等，针对这些系统，有时需要考虑在既定的网络中能通过网络的最大流量是多少，这就产生了网络的最大流问题；有时需要考虑在满足成本最低的前提下，使网络承载一定的流量，这就产生了网络的最小费用流问题；有时也需要考虑在满足成本最低的前提下，使网络通过的流量达到最大，这就产生了网络的最小费用最大流问题。这些问题可以说是线性规划问题，用线性规划的方法也可以解决，但依据现实问题抽象出来的网络模型具有特殊的结构，而且网络模型也具有直观性，所以基于网络模型可以设计出比单纯形法更为有效的的算法来解决这类问题。17十一月2025第77页第9章图与网络

为了更形象地的学习网络流的相关知识，下面给出一个引例：某运输企业