6.3 最短路问题

数学学习 · 爱知数学讲义

18
本章目录 · 3 节

本章导读

【定义6.3.1:带权图】给无向图或有向图 的每条边赋一个实数权,写成函数 ,所得图记为 。边 连接 时也可写 ,但若有平行边且权不同,必须保留边身份,不能只凭端点唯一确定权。

通路 的长度为 ,回路同样定义。这里按经过边的次数求和:同一条边重复走两次,就把权加两次;不能只对去重后的边集合求和。权可表示距离、时间、费用等,计算时单位必须统一。

本节三类问题为最短路、中国邮递员、货郎担问题,默认边权非负。可达的 间,最短路径的长度称距离 ;约定 ,不可达时 。有向图的距离按方向计算,不必对称。非负性保证可删去重复顶点之间的回路而不增加长度,所以存在一条无多余绕行的最短路径,零权回路不影响最短距离。

【最短路径的子路径性质】若从 到 的最短路径经过顶点 ,其从 到 的前段也必为最短路径;否则替换为更短的前段,就得到更短的全程,与最优性矛盾。同样,任意两中间顶点之间的子路径也最短。这是标号法逐步确认距离的依据。

【迪杰斯特拉标号法】给定非负权图和源点 ,为每点维护标号 。永久标号的 已等于 , 为最短路径上的前驱;临时标号只是当前已知的上界。初始化 、其余为 ,源点前驱记自身,其他前驱在未发现路径前记“未定义”。

每一步在尚未永久标号的顶点中选 最小的点 ,把它永久化;对从 能沿边到达的各临时点 ,若 ,就令 、。无向边可用于两个方向,有向图只能按出弧松弛。重复到全部可达点永久化;若剩下临时点的最小值已为 ,它们都不可达,可以停止。

同值并列时任选其一永久化即可,可能得到不同但同样短的路径。本节为与教材表一致,例题中用顶点编号优先打破并列。回溯前驱直到 得到路径的逆序,再反转;不可达点没有实际路径,不能把初始化前驱当作存在一条边。零边权允许,负边权不能直接套用本算法。

正确性要点:若最小临时标号 还有更短未发现路径,沿该路径取第一个未永久标号的点 ,其前一顶点已经永久化,故松弛后 不超过该路径到 的长度;又后续边权非负,可得 ,与选 为最小矛盾。简单数组实现时间为 ;用邻接表和优先队列可加速稀疏图,但永久标号与非负权的逻辑不变。

例6.3.1:从v1出发的最短路

37526332822v1v2v3v4v5v6v7
图6.3.1:七顶点非负带权图,数字均为边权

表6.3.1重排如下:每行列出“本步选择的永久顶点”及该时刻的全体标号。已选顶点集在行首列出,未定义前驱记 ;标号第一项用前驱编号代替 的完整下标,以压缩宽度。全部标号顺序始终为 。

第1步,永久点 :。

第2步,永久点 :。

第3步,永久点 :。

第4步,永久点 :。

第5步,新选 ,永久点 :。

第6步,新选 :,仅 尚为临时标号。

第7步,新选 :标号数值与上一步相同,所有顶点均已永久化。过程在永久化一个点后松弛它的邻点,再选择下一点,因此第1行保留教材的“源点已永久化、尚未进行第一次松弛”状态。

最终路径与距离分别为:到 走 ,距离3;到 走 ,距离5;到 走 ,距离5;到 走 ,距离8;到 走 ,距离7;到 走 ,距离9。(例完)

【中国邮递员问题】在连通的无向非负带权图中,从邮局出发,经过每条边至少一次并返回邮局,求总长度最小的路线。这与哈密顿问题不同:顶点、边都允许重复,但全部边必须覆盖。管梅谷于1962年提出该问题。

若图本来欧拉,任意欧拉回路只走每边一次,长度就是全部边权之和,已达到显然的下界。若有奇度顶点,则须补走一些边,使各点总的经过次数配对。对奇度点集合计算两两最短距离,再把奇度点分成若干对,选择最短距离总和最小的配对;沿各对的最短路径把原边复制一遍,在所得偶度连通多重图中求欧拉回路,就得到最优路线。

为何不能随便配对:任何闭合覆盖路线相对于原图多走的边组成一个多重图,其奇度点恰为原来的奇度点。这些附加边可拆成奇度点之间的配对通路及若干回路;非负回路可删,配对通路的长度不小于相应最短距离。因此最小配对成本给出所有可行附加走法的下界,而复制最优配对最短路恰能达到。图不连通且要求覆盖所有边时,本来就不存在这样的单一路线。

例6.3.2:街区投递路线

766664553243352524abcdefghijkl
图6.3.2(a):十二路口、十八街段,边权单位为百米

邮局在 ,原街道总长度为78个单位,即7800米。奇度顶点为 。三种配对必须全部比较: 成本 ; 成本 ; 成本 。其中 到 的最短路是 ,长度 ,不是直接按画面直线距离估计。

所以补走 各一次,附加长度11。复制后的图如下,浅蓝色曲线表示额外经过的一份边,不是新建道路。

766664553243352524abcdefghijkl
图6.3.2(b):复制bc、ei、ij,使所有度数变偶

一条最优闭合路线按路口顺序为 。它包含原来全部18条边,对 各多走一次,21次街段行走的总长度为 个单位,即8900米。路线可有其他等价走法,判据是闭合、覆盖、总长度达到下界。(例完)

【货郎担问题,又称旅行商问题】给出 个城市及两两之间的非负交通成本,求经过每城恰好一次并回到起点的最短路线。可以形式上把缺失道路的成本记 ,但若每条哈密顿回路都含无限权边,就不存在有限成本的可行路线,不能把“最优值为无穷”误报为已找到实际路线。

图论表述是在带权完全图中寻找总权最小的哈密顿回路。与最短路不同,它必须访问全部顶点;与中国邮递员不同,它没有覆盖所有边的要求。若把道路网先转换成城市之间的最短距离矩阵,还须明确“城市”只指要求拜访的那些点,两个城市间的最短路可能经过其他路口,不能把这种建模与原图每个顶点恰访一次的严格条件混用。

132234abcd
图6.3.3(a):四城完全带权图

四城例子中边权为 。忽略起点的循环移位和反向,只有三种回路。

1322abcd
图6.3.3(b):C1为a-b-c-d-a,长度8

,长度 。

1324abcd
图6.3.3(c):C2为a-b-d-c-a,长度10

,长度 。

2334abcd
图6.3.3(d):C3为a-d-b-c-a,长度12

,长度 ,所以 为最优。三种是忽略起点和方向后的实际路线数,不是按每个顶点排列都单独计数。

教材把一般旅行商优化问题列为NP难问题。“难”不等于不能计算:小规模可穷举,较大规模可用动态规划、分支定界等精确方法或适当近似方法;其中启发式给出的路线不能未经证明就宣称是全局最优。本例通过穷尽三种回路得到最优性证明,而不是只画一条看起来较短的路线。