【梳理】离散数学 第15章 欧拉图与哈密顿图 15.3 最短路问题、中国邮递员问题与货郎担问题

教材：《离散数学》第2版 屈婉玲 耿素云 张立昂 高等教育出版社
源文档高清截图在最后

15.3 最短路问题、中国邮递员问题与货郎担问题

1、设图G(V, E)，给定W：E→R，对G的每一条边e，称W(e)为边e的权，把这样的图G称为带权图，记为G(V, E, W)或G = <V, E, W>或G = (V, E, W)。当e = (u, v)（或<u, v>）时，也可以把W(e)记作W(u, v)。

2、设P是G的一条通路，P中所有边的边权之和称为P的长度W§。类似定义回路C的长度W©。

3、设带权图G(V, E, W)，且每一条边的权都是非负实数。对任意u，v∈V，当u和v连通（u可达v）时，称从u到v长度最短的路径为u到v的最短路径，该路径的长度称作距离d(u, v)。约定d(u, u) = 0，当u不可达v时d(u, v) = ∞。

4、Dijkstra算法
输入：带权图G(V, E, W)和s∈V，其中|V| = n，对任意e∈E，W(e)≥0。
输出：s到G中每一个点的最短路径及距离。
记每一个顶点的标号L(v) = (L1(v), L2(v))。标号分为永久标号和临时标号。对永久标号，L1(v)和L2(v)分别是：s到v的最短路径上v的前一个顶点；s到v的距离。对临时标号，L1(v)和L2(v)分别是：当前从s经过已永久标号的点到达v的最短路上v的前一个顶点；这条路径的长度。
【1】L(s) = (s, 0)，L(v) = (s, +∞)，v∈V – {s}，i = 1。L(s)是永久标号，其余均为临时标号，u = s。
【2】对u邻接的临时标号的顶点v：
如果L2(u) + W(u, v) < L2(v)，那么令L(v) = (u, L2(u) + W(u, v))。
【3】计算L2(t) = min{L2(v) | v∈V且有临时标号}，把L(t)改为永久标号。
【4】如果i < n，那么令u = t，i = i + 1，返回到【2】继续。
计算完毕后，对每一个顶点u，都有d(s, u) = L2(u)。利用L1(v)从u开始回溯，查找从s到u的最短路径。

5、中国邮递员问题（邮递员问题、中国邮路问题）：邮递员从邮局出发，走遍负责街区投递邮件，最后回到邮局。问：如何走才能使他走的路最短？
对应的图论模型是：给定一个带权无向图，所有边权均非负，求每一条边至少经过一次的最短回路。该问题由管梅谷于1962年首度提出，故称中国邮递员问题。
如果存在欧拉回路，那么任意一条欧拉回路都是正解，经过每一条欧拉回路走过的距离都是一样的，均为所有边的边权之和。如果不存在欧拉回路，那么由于每一条边都会贡献两个度，图的总度数一定是偶数，所以奇度顶点的个数只能是偶数。那么，把奇度顶点每两个分一对，枚举全部组合，求出重复部分的最短距离，即令每一对奇度顶点中一个点到另一个点的最短距离之和最小，再加上原有的全部边的边权和即为答案。

6、货郎担问题（旅行商问题）：有n个城市，给定城市之间的道路长（为正无穷大时代表两个城市之间不连通）。一个旅行商从某城出发，要求仅经过每个城市一次，最后回到出发城市。问：如何走才能使他走的路线最短？
对应的图论模型是：设n阶带权图G(V, E, W)，求G的一条最短的哈密顿回路。
该问题属于NP问题中的一个，目前没有找到有效的时间复杂度可以接受的算法求解。虽然可以采用动态规划求解，但其时间复杂度仍然是指数级的。
NP完全问题（NPC问题）是世界七大数学难题之一。首先明确几个定义：
（1）P问题。这类问题具有多项式的时间复杂度的确定的算法。即对于一切合法的输入，都能在多项式的时间内给出结果。对于一个尚未验证正确性的解，要验证其是否正确，时间复杂度自然也是多项式的。
（2）NP问题。这类问题目前尚未找到具有多项式的时间复杂度的确定的算法，但对于每个可能的解，都可以在多项式时间内对正确性完成验证。
（3）NPC问题。如果全部的NP问题都能转化成一个很复杂的问题去求得多项式时间的“通法”，以至于只要解决了这个最复杂的问题，那么其余的NP问题都可以在多项式的时间复杂度内完成求解。也就是说，NP问题实际上都是P问题，即NP = P。NP完全问题的核心内容就是“NP = P？”，即：是否所有能在多项式的时间内验证一个解的问题，都具有一个确定的时间复杂度为多项式的算法？
比如我们已知解一元、二元、三元、四元的线性方程组的算法。我们把这个问题不断推广，推广到n元线性方程组，如果对n元线性方程组能找到多项式的时间复杂度的算法，那么这个算法就可以套用去解一、二、三、四、……元的线性方程组。NP问题转化到NPC问题的思想也是类似的。