专栏首页程序员维他命最短路验证九省通衢

最短路验证九省通衢

九省通衢的武汉

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

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

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

这句话听起来有点绕,其实就是从湖北省出发,到任一一个省份,途中只需要经过小于等于 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 公里等等。这所有的一切都在告诉大家要注意个人防护,戴口罩、勤洗手!

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

本文分享自微信公众号 - 程序员维他命(J_Knight_)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-02-02

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 图解 LeetCode 链表: 82. Remove Duplicates from Sorted List II

    今天是 LeetCode 算法的 第 1 阶段第 2 天 ,这一阶段主要学习链表相关的算法题和链表数据结构。这道题是上一道的升级版。

    用户2932962
  • 面向对象设计的设计模式(三):抽象工厂模式

    有时候我们需要一个工厂可以提供多个产品对象,而不是单一的产品对象。比如系统中有多于一个的产品族,而每次只使用其中某一产品族,属于同一个产品族的产品将在一起使用。

    用户2932962
  • 带你入门 DissCode,从而攻克大厂面试题!

    今年七月份,我开始写公众号。有两个目的,第一是为了增加自己在技术圈内的影响力,第二是促进更多人来重视算法。于是我写了一系列文章来讲解一些大学课本上有的但是被很多...

    用户2932962
  • Linux下分布式系统以及CAP理论分析

    CAP理论被很多人拿来作为分布式系统设计的金律,然而感觉大家对CAP这三个属性的认识却存在不少误区,那么什么是CAP理论呢?CAP原本是一个猜想,2000年PO...

    洗尽了浮华
  • 软件质量报告模板-产品质量度量

    顾翔老师开发的bugreport2script开源了,希望大家多提建议。文件在https://github.com/xianggu625/bug2testscr...

    小老鼠
  • 猿设计11——真电商之促销的玩法你真的知道吗?

    经过前面几章的讨论相信你对类目和商品体系有了一定的认识。众所周知,建立类目体系的目的是为了更好地管理和维护商品。建立商品的唯一目的就是销售。从最基础的目的出发,...

    山旮旯的胖子
  • java设计模式--组合

    import java.util.ArrayList; import java.util.List;

    曼路
  • 国标GB28181视频流媒体平台EasyGBS设备注册无法显示通道数量问题排查

    用过国标流媒体服务器的朋友们应该都知道,GB28181协议是公安部提出来的,能够对接公安部的网络系统,给安防带来了很大的便利性,我们的国标流媒体服务器就支持集成...

    EasyNVR
  • 深度学习简易入门

    深度学习是机器学习中的一个重要的方向,深度学习其实就是神经网络学习,这里“深度”就是说神经网络中众多的层。那么深度学习是用来干嘛的呢?

    jennyxia
  • 华为防火墙VRRP双机热备的原理及配置

    一、何为双机热备? 所谓的双机热备无非就是以7X24小时不中断的为企业提供服务为目的,各种双机热备的技术很多,那么华为使用了这个共有协议的热备协议——VRRP。

    小手冰凉

扫码关注云+社区

领取腾讯云代金券