最短路验证九省通衢

2020 年 2 月 25 日
笔记

九省通衢的武汉

这两天新型冠状病毒真的是让人心惊胆战。病毒传播速度的快从官方给出的数字就能体现出来。在传播的背后其实还隐藏着这么一个问题：为什么很多人都会从湖北出发，或者途经湖北省呢？

大约在去年年底，我在微博上看见了这么一个热搜：武汉到任一省级行政区最多只需要跨越两个省级行政区。

微博热搜 #武汉到任一省级行政区最多跨两个

这句话听起来有点绕，其实就是从湖北省出发，到任一一个省份，途中只需要经过小于等于 2 个省份就能到达。在这条微博上还给了三个例子：

几个例子

当然这里有一些不严谨的地方就是广西省和海南省其实是隔海相望的，在这里我们也假定它俩是相邻的。那事实真的是如此吗？

模型抽象

我们可以把所有省份全部都抽象成一个节点，然后将相邻的节点建边。这样我们就将中国省级行政区抽象成了多个节点。下面的动图展示了建图过程：

模拟建图过程

为了建立图的边连接关系，我将所有省级行政区的相邻关系已经整理了出来，其结果如下：

北京市：河北省、天津市  天津市：北京市、河北省  上海市：浙江省、江苏省  重庆市：四川省、贵州省、陕西省、湖北省、湖南省  河北省：山东省、河南省、山西省、内蒙古自治区、辽宁省、天津市、北京市  山西省：内蒙古自治区，陕西省，河南省，河北省  辽宁省：吉林省、内蒙古自治区、河北省  吉林省：内蒙古自治区、辽宁省、黑龙江省  黑龙江省：吉林省、内蒙古自治区  江苏省：山东省、安徽省、浙江省、上海市  浙江省：江苏省、安徽省、上海市、江西省、福建省  安徽省：山东省、江苏省、浙江省、江西省、湖北省、河南省  福建省：浙江省、江西省、山东省、台湾省（隔海相望）  江西省：安徽省、浙江省、福建省、广东省、湖南省、湖北省  山东省：河北省、河南省、安徽省、江苏省  河南省：河北省、山东省、江苏省、安徽省、湖北省、陕西省、山西省  湖北省：河南省、安徽省、江西省、湖南省、重庆市、陕西省  湖南省：湖北省、江西省、广东省、广西壮族自治区、贵州省、重庆市  广东省：福建省、江西省、湖南省、广西壮族自治区、海南省（隔海相望）、香港市、澳门市  海南省：广东省  四川省：青海省、甘肃省、陕西省、重庆市、贵州省、云南省、新疆维吾尔自治区、西藏自治区  贵州省：四川省、重庆市、湖南省、广西壮族自治区、云南省  云南省：西藏自治区、四川省、贵州省、广西壮族自治区  陕西省：内蒙古自治区、陕西省、河南省、湖北省、重庆市、四川省、甘肃省、宁夏回族自治区  甘肃省：内蒙古自治区、宁夏回族自治区、陕西省、四川省、青海省、新疆维吾尔自治区  青海省：新疆维吾尔自治区、甘肃省、四川省、西藏自治区  台湾省：福建省  内蒙古自治区：甘肃省、宁夏回族自治区、陕西省、陕西省、河北省、辽宁省、吉林省、黑龙江省  广西壮族自治区：云南省、贵州省、湖南省、广东省  西藏自治区：新疆维吾尔自治区、青海省、四川省、云南省  宁夏回族自治区：内蒙古自治区、陕西省、甘肃省  新疆维吾尔自治区：甘肃省、青海省、西藏自治区  香港市：广东省  澳门市：广东省

文本数据预处理

上面的数据文本数据来源有两个地方，一个是通过 Google 搜出的，另外一部分是笔者通过省级行政区板块图自己数出来的。

desc = """北京：河北、天津  天津：北京、河北  上海：浙江、江苏  重庆：四川、贵州、陕西、湖北、湖南  河北：山东、河南、山西、内蒙古、辽宁、天津、北京  山西：内蒙古、陕西、河南、河北  辽宁：吉林、内蒙古、河北  吉林：内蒙古、辽宁、黑龙江  黑龙江：吉林、内蒙古  江苏：山东、安徽、浙江、上海  浙江：江苏、安徽、上海、江西、福建  安徽：山东、江苏、浙江、江西、湖北、河南  福建：浙江、江西、山东、台湾  江西：安徽、浙江、福建、广东、湖南、湖北  山东：河北、河南、安徽、江苏  河南：河北、山东、江苏、安徽、湖北、陕西、山西  湖北：河南、安徽、江西、湖南、重庆、陕西  湖南：湖北、江西、广东、广西、贵州、重庆  广东：福建、江西、湖南、广西、海南、香港、澳门  海南：广东  四川：青海、甘肃、陕西、重庆、贵州、云南、新疆、西藏  贵州：四川、重庆、湖南、广西、云南  云南：西藏、四川、贵州、广西  陕西：内蒙古、陕西、河南、湖北、重庆、四川、甘肃、宁夏  甘肃：内蒙古、宁夏、陕西、四川、青海、新疆  青海：新疆、甘肃、四川、西藏  台湾：福建  内蒙古：甘肃、宁夏、陕西、陕西、河北、辽宁、吉林、黑龙江  广西：云南、贵州、湖南、广东  西藏：新疆、青海、四川、云南  宁夏：内蒙古、陕西、甘肃  新疆：甘肃、青海、西藏  香港：广东  澳门：广东  """    import re    datas = desc.split('n')  cities = {}    # 数据处理  for line in datas:      m = re.match(r'^(.+?)：(.+?)$', line)      if m:          current_city = m.groups(2)[0]          link_cities_data = m.groups(2)[1]          current_link_cities = []          for link_city in link_cities_data.split('、'):              current_link_cities.append(link_city)          cities[current_city] = current_link_cities    print(cities)    """  {'北京': ['河北', '天津'], '天津': ['北京', '河北']...  """

通过对字符串的处理和正则匹配捕获，我们获得一个字典，Key 是每个省级行政区，Value 是一个数组，也就是和它相邻的省级行政区。如此，我们将一份省级行政区相邻的关系数据转换成为了一个无向图。

单源最短路的使用

所谓单元最短路就是计算单一起点（源点）到图中任一一个节点的最短路径是多少的算法。具体在刷题时或者信息学竞赛中常用的只有三种算法：Dijkstra 算法、Bellman-Ford 算法以及 SPFA 算法。这些算法我会在后续专门讲解单源最短路时对每个算法逐一讲述，本文只是一个对单源最短路算法的一个最简单的实践和应用。

继续来思考“到任一省级行政区最多只需要跨越两个省级行政区“这句话，转换成图的描述，其实就是到任一节点的最短路径上，只有小于等于 4 个节点、3 条边。更进一步的，假设我们每一条边的权值都为 1 ，那么只要满足单源到任一节点的最短路径是 ≤ 3 即可证明。

单源最短路

这里我使用 Dijkstra 算法来做此次验证过程。我先给出代码，在后文中再做简单的解释：

# ... 接上文数据处理代码    # 节点离散化  city_hash = {}  index = 0  for city in cities.keys():      city_hash[city] = index      index += 1  re_city_hash = {v: k for k, v in city_hash.items()}    # 描述图  class Edge:      def __init__(self, to: int, cost: int):          self.to = to          self.cost = cost      INF: int = 10 ** 8  # 代表无限大  V: int = len(city_hash)  # 节点数  G: [[Edge]] = [[] for _ in range(V)]  # 临界表  d: [int] = [INF] * V  # 最短距离    # 建图  for f, tos in cities.items():      for to in tos:          G[city_hash[f]].append(Edge(to=city_hash[to], cost=1))    # 最短路算法  import queue  def dijkstra(s: int):      que: queue.PriorityQueue = queue.PriorityQueue()      d[s] = 0      que.put((0, s))      while que.qsize() > 0:          p = que.get()          v = p[1]          for i in range(len(G[v])):              e: Edge = G[v][i]                          # 松弛操作              if d[e.to] > d[v] + e.cost:                  d[e.to] = d[v] + e.cost                  que.put((d[e.to], e.to))    dijkstra(s=16)  # print(city_hash)  for i, k in enumerate(d):      print(f'{re_city_hash[i]}: {k}', end='t')    """  北京: 3  天津: 3  上海: 3  重庆: 1  河北: 2  山西: 2  辽宁: 3  吉林: 3  黑龙江: 3  江苏: 2  浙江: 2  安徽: 1  福建: 2  江西: 1  山东: 2  河南: 1  湖北: 0  湖南: 1  广东: 2  海南: 3  四川: 2  贵州: 2  云南: 3  陕西: 1  甘肃: 2  青海: 3  台湾: 3  内蒙古: 2  广西: 2  西藏: 3  宁夏: 2  新疆: 3  香港: 3  澳门: 3  """

上述代码的简单说明

使用二维数组

G: [[Edge]] = [[] for _ in range(V)]  # 临界表

这段代码中，G 的第一维代表每一个节点，第二维是一个数组，代表所有的边。其实这种结构就巧妙的描述了一个图节点数据结构。其实这里是利用了 Python 中的 List 可扩容的特点，比较巧妙的将节点组成了一个“链式“结构（其实就是下标的连续性）。

这种图描述的数据结构在信息学竞赛中有一个独特的名字叫：链式前向星（邻接表的另一种表达方式），不同于以往邻接表的方式就是遍历方式。

什么是松弛操作？

if d[e.to] > d[v] + e.cost:      d[e.to] = d[v] + e.cost

我们通过一种类比来解释一下什么是松弛：假设墙上有如图 4 个钉子，一个橡皮筋现在使用交叉的方式从钉子 1 绑到钉子 2，再从钉子 2 绑到钉子四。现在我将钉子 2 上绑的皮筋摘下换成钉子 3，于是橡皮筋由此得到松弛。

橡皮筋的松弛状态

这个比喻十分形象。假设我们将四个钉子作为四个节点，而目标是从节点 1 途经节点 2 或者节点 3 走到节点 4 ，此时最短路径就是 1 → 3 → 4。而对应的，这个松弛操作就是在反复的更新 1 → 4 的最短路径。

回归到 Dijkstra 算法，这里的松弛操作是对边的一种松弛。

回归到实际问题

我们通过对省级行政区抽象成图，并且给每一条边赋权，从而验证了武汉到任一一个省级行政区最多只需要跨越两个省级行政区的冷知识。所以从一定角度上，也解释了为什么此次肺炎传播速度之快的些许原因。

当然也许你会说，每个省份也有面积的大小之分，所以单从省级跨越的个数角度是十分不严谨的。当然确实是这样，这里只是想通过最短路算法的角度，来简单的验证这个问题，实际问题肯定还需要具体的分析，才能证明传播速度之快的结论，比如：春运客流量猛增、华南海鲜市场到汉口火车站的距离只有 1 公里等等。这所有的一切都在告诉大家要注意个人防护，戴口罩、勤洗手！

后续的文章也会继续深入地介绍最短路等图论问题，当然如果你有更想了解的内容，也欢迎在文章下方留言。最后祝大家新年快乐，身体健康。