最短路驗證九省通衢
- 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 公里等等。這所有的一切都在告訴大家要注意個人防護，戴口罩、勤洗手！
後續的文章也會繼續深入地介紹最短路等圖論問題，當然如果你有更想了解的內容，也歡迎在文章下方留言。最後祝大家新年快樂，身體健康。
