解决最短路问题

子任务5.1　解决最短路问题

5.1.1　任务引入

【任务5-1】　求图5-1中v₁到v₆的最短路。

图5-1

5.1.2　任务分析

最短路问题是图论中十分重要的最优化问题之一，它作为一个经常被用到的基本工具，可以解决实际物流中的许多问题，比如输送管道铺设、运输线路安排、配送中心选址、设施设备更新等，也可以用于解决其他的最优化问题。

最短路问题的算法较多，这里主要介绍狄克斯屈标号法。狄克斯屈标号法是狄克斯屈在1959年提出的，适用于所有权数均为非负（即一切w_ij≥0，w_ij表示顶点v_i与v_j的边的权数）的网络，能够求出网络的任一点v_s到其他各点的最短路，为目前求这类网络最短路的最好算法。其基本思路是：若（v₁，v₂，…，v_n-1，v_n）是从v₁到v_n的最短路径，则（v₁，v₂，…，v_n-1）也必是从v₁到v_n-1的最短路径。这个算法实际上也给出了寻求从一个初始定点v_s到任意一个点v_j的最短路。

下面来介绍一下狄克斯屈标号法的算法步骤。

首先规定：P（v_j）为从始点v_s到v_j的最短距离，是固定标号；

T（v_j）为从始点v_s到v_j的最短距离上界，是临时标号；

P（v_s）=0，这表示从v_s到v_s的最短距离为0；

T（v_j）=+∞（j=2，3，…，n）。

①给始点v_s以P标号P（v_s）=0，可用“（）”标出；其余节点均给T标号，T（v_j）=+∞（j=2，3，…，n），可不标出。

②设节点v_i为刚得到P标号的点，考虑点v_j，其中（v_i，v_j）∈E，且v_j为T标号。对v_j的T标号进行如下修改：T（v_j）=min［T（v_j），P（v_i）+w_ij］。

③比较所有具有T标号的节点，把最小者改为P标号，即：P（v_k）=min［T（v_j）］。

当存在两个以上最小值时，可同时改为P标号。若全部节点均为P标号，则停止，否则用v_k代替v_j，返回步骤②，直到所有点都标上P标号。

5.1.3　知识建构

案例导入

格尼斯堡七桥问题

图论是近20年来发展十分迅速，应用十分广泛的运筹学分支。在许多领域，如物理学、化学、计算机科学、控制论、信息论、网络理论、社会科学以及经济管理各方面都有广泛的应用。

早期图论与“数学游戏”有密切的关系，1736年欧拉发表了有关图论方面的第一篇论文，解决了当时很有名的哥尼斯堡城七桥问题。该问题是：哥尼斯堡城中有一条河叫普雷格尔河，该河中有两个岛，河上有七座桥把普雷格尔河中的两个小岛与河两岸连接起来，如图5-2（a）所示。

当时那里的居民热衷于这样的问题：从河岸或岛上任何一个地方开始，能否通过每一座桥一次且仅一次回到原地？1736年欧拉将此问题归结为如图5-2（b）所示的一笔化问题，即能否从某一点开始一笔画出这个图形，最后回到原点，而不重复。欧拉证明了这是不可能的，因为图5-2（b）中的每一点都只与奇数条线相关联，不可能将这个图不重复地一笔画成。这是古典图论中的一个著名问题。随着信息技术的发展，以及经济全球化、一体化进程加剧，物流越来越成为一个庞大的系统，许多物流问题都需要运用图论的方法来帮助解决。例如：客户要求第三方物流公司在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网络纵横交错，因此有多种行车路线可供选择，第三方物流公司将怎样给他的司机规划运输路线呢？假如运输车辆的行驶速度一定，那么这一个问题可转化为图论中的问题，即在甲地和乙地之间所有可选择的路线中去寻找到一条最短路径。

图5-2　格尼斯堡七桥问题

1）图的基本概念

在自然界和人类社会中，大量的事物以及事物之间的关系，常常可以用图形来描述。物质结构、电路网络、城市规划、交通运输、信息传递、物资调配等问题都可以用电和线连接起来的图进行模拟。

［示例］为了反映我国北京、上海等10个城市间的铁路分布情况，可以用点来代表城市，用点和点之间的连线代表这两个城市之间的铁路线，如图5-3所示。

［示例］为了反映5家企业间的业务往来关系，可以用点表示企业，用点和点之间的连线表示两家企业之间具有的业务联系，则企业间的业务往来关系可用图5-4来描述。

［示例］某单位储存8种化学药品，其中某些药品是不能存放在同一个库房里的，因此，可以通过网络图来描述这个情况。可以用点来表示这8种药品，若两者之间不能存放在同一个库房，则在两者之间连线，如图5-5所示。

图5-3　十城市铁路图

图5-4　企业业务关系图

图5-5　化学药品存放图

由上述三个例子可见，图是由代表所研究对象的点和表述对象之间关联性质的线构成的，一般称为点线图。图5-3、图5-4、图5-5都是点线图。其中，图的线不添加表示关联方向的箭头，一般称为边，这样的图称为无向图；图的线带有表示关联方向的箭头，一般称为弧，这样的图称为有向图。

由图5-3、图5-4、图5-5可见：

①一个图G是由顶点的集合V=｛v₁，v₂，…，v_n｝和表示事物之间关联性质的边的集合E=｛e₁，e₂，…，e_m｝组成的，记为G=（V，E）。其中V中元素的个数称为图G的顶点数，E中元素的个数称为图G的边数。

②关联性质：

a.相邻点：关联同一条边的两顶点称为相邻点。例如，图5-3中v₁和v₂，v₂和v₄等都称为相邻点。

孤立点：与任何边都没有关联的顶点称为孤立点。

b.相邻边：边集E中每一条边都关联两个顶点v_i和v_j。所以边e_i可用点集V中的无序元素对［v_i，v_j］表示。关联同一个顶点的两条边称为相邻边。如图5-3中［v₁，v₂］和［v₂，v₄］就是相邻边。

多重边：关联于两个相邻顶点的边称为多重边。如图5-3中，从杭州到广州可能有两条铁路线，那么这两条铁路线就称为图5-3的多重边。

环：两端点接于同一顶点的边称为环。

③点的次数（度数）。与点v_i关联的边数称为点的次数（度数），记为d（v_i），如d（v_i）=5，称顶点v_i的次数为5，或顶点v_i为5度关联，即与顶点v_i关联的边有5条。例如，在图5-4中，d（v₁）=4，则说明v₁为4度关联，即企业1与4个企业有业务往来关系。

奇点：次数（度数）为奇数的点称为奇点。

偶点：次数（度数）为偶数的点称为偶点。

悬挂点：次数（度数）为1的点称为悬挂点。

悬挂边：与悬挂点相关联的边称为悬挂边。

④简单图。无环无多重边的图称为简单图。如图5-4、图5-5均为简单图。

多重图：含有多重边的图称为多重图，如图5-3。

2）连通图

①链：图中从某点开始的点边交替序列称为链。如图5-4中，（v₁，e₁，v₂，e₇，v₃，e₆，v₄）称为一条链。

闭链（圈）：首尾相连的链称为闭链（或圈），否则称为开链。如图5-4中，（v₁，e₁，v₂，e₇，v₃，e₆，v₄，e₅，v₅，e₄，v₁）称为一条闭链（圈）。

简单链：若在一条链中，所有的边e_i均不相同，则称此链为简单链。若顶点v_i也各不相同（对闭链来说，除第一个顶点和最后一个顶点相同外），则称为初等链。如链（v₁，e₁，v₂，e₇，v₃，e₆，v₄）和闭链（圈）（v₁，e₁，v₂，e₇，v₃，e₆，v₄，e₅，v₅，e₄，v₁）均既为简单链，也为初等链。

②路：初等链也称为路。如（v₁，e₁，v₂，e₇，v₃，e₆，v₄）。

回路：首尾相连的路称为回路，如（v₁，e₁，v₂，e₇，v₃，e₆，v₄，e₅，v₅，e₄，v₁）。

③连通图：一个图G的任意两顶点之间，如果均至少有一条链将它们连接起来，则这个图G称为连通图，否则称为不连通图。如图5-3、图5-4、图5-5均为连通图。

3）子图

设有图G₁=｛V₁，E₁｝，G₂=｛V₂，E₂｝，如图5-6所示。

图5-6　子图

①子图：设G₁=｛V₁，E₁｝，G₂=｛V₂，E₂｝，如果图G₁=｛V₁，E₁｝的顶点集V₁是图G₂=｛V₂，E₂｝的顶点集V₂的一部分，边集E₁是E₂的一部分，即V₁⊆V₂，E₁⊆E₂，则称G₁=｛V₁，E₁｝为G₂=｛V₂，E₂｝的子图。如图5-6（b）为图5-6（a）的子图。

②真子图：若V₁⊂V₂，E₁⊂E₂，即G₁=｛V₁，E₁｝中不包含G₂=｛V₂，E₂｝中所有的顶点和边，则称G₁是G₂的真子图。如图5-6（c）为图5-6（a）的真子图。

③部分图：若V₁=V₂，E₁⊂E₂，即G₁中包含G₂中所有的点，但不包含G₂中所有的边，则称G₁是G₂的一个部分图。如图5-6（d）为图5-6（a）的部分图。

④支撑子图：若G₁是G₂的部分图，且G₁是连通图，则称G₁是G₂的支撑子图。如图5-6（e）为图5-6（a）的支撑子图。

⑤生成子图：若G₁是G₂的真子图，且G₁是不连通图，则称G₁是G₂的生成子图。如图5-6（f）为图5-6（a）的生成子图。

5.1.4　任务实施

对任务5-1进行任务实施

第一步：首先给v₁以P标号，P（v₁）=0，给其余所有点T标号，T（v_j）=+∞（j=2，3，…，6）。P标号以“（）”形式标在结点旁边，T标号以不带“（）”的数字标在结点旁，如图5-7所示。

第二步：考察v₁。

T（v₂）=min［T（v₂），P（v₁）+a₁₂］=min［+∞，0+3］=3

T（v₃）=min［T（v₃），P（v₁）+a₁₃］=min［+∞，0+5］=5

所以，P（v₂）=3，如图5-7所示。

第三步：考察v₂。

T（v₃）=min［T（v₃），P（v₂）+a₂₃］=min［5，3+1］=4

T（v₄）=min［T（v₄），P（v₂）+a₂₄］=min［+∞，3+6］=9

所以，P（v₃）=4，如图5-7所示。

第四步：考察v₃。

T（v₅）=min［T（v₅），P（v₃）+a₃₅］=min［+∞，4+1］=5

T（v₄）=min［T（v₄），P（v₃）+a₃₄］=min［9，4+4］=8

所以，P（v₅）=5，如图5-8所示。

第五步：考察v₅。

T（v₆）=min［T（v₆），P（v₅）+a₅₆］=min［+∞，5+6］=11

T（v₄）=min［T（v₄），P（v₅）+a₅₄］=min［+∞，5+2］=7

所以，P（v₄）=7，如图5-8所示。

图5-7

图5-8

第六步：考察v₄。

T（v₆）=min［T（v₆），P（v₄）+a₄₆］=min［11，7+3］=10

所以，P（v₆）=10所有点都标上P标号，如图5-9所示。

第七步：标出最短路：v₁到v₆的最短路可从v₁开始，根据永久性标号数值回溯得到。

最短路径是：v₁→v₂→v₃→v₅→v₄→v₆，路长为10。同时得到，到其余各点的最短路，即各点的永久性标号P（v_i），如图5-10所示。

图5-9

图5-10