圖的最短路徑之楊貴妃荔枝自由
- 2021 年 3 月 18 日
- 筆記
背景
《新唐書》記載，楊貴妃嗜荔枝，必欲生致之，乃置騎傳送，走數千里，味未變，已至京師。
正文
此時已是二更天，我仍無心睡眠。
今日皇帝剛剛下旨，命令我們這些差管將剛剛成熟的荔枝送往京城，必須新鮮，否則就地問斬。
可蜀中到長安數千里，途徑數十城市，如何尋得最短路徑，將新鮮荔枝送入皇宮呢？
夜不能寐，便掌了一盞燈，坐在書房苦思。
夫人聽見了動靜，來到我旁邊，看我唉聲嘆氣，便寬慰到:”相公，事到如此也無甚好辦法。皇命不可違，我們只能走一步看一步吧。”
我聽了，無奈搖搖頭，喃喃到:”若找不到最短路徑，我們就是日夜Benz，快馬加鞭，也無法完成皇命啊，怎麼能說走一步看一步，走一步看一步。。。”
這時，我突然想到了什麼，拿出紙和筆，推算了一遍，我似乎找到了破解之法。
夫人湊近問道：”相公可是尋得什麼法子？”
我笑到:”還是夫人提醒了我啊，這個法子就是 走一步看一步！”
“哦，這是何意？”
我在紙上畫到
“夫人請看，我們可以畫個簡略的從蜀中到長安的地圖。
如圖所示，當前我們身處蜀中，從蜀中到長安有可能途經任何一個城市。
但從從蜀中來看，我們可去的城市只有佳城 宜城 二城，距離分別是4和5。
即
按照夫人所言，走一步，那我們就去離蜀中最近的城市，即佳城。
假設我們已經到了佳城，環城四顧，也就是看一步，發現還沒有去過並且相鄰的城市有 宜城，冰城。
我們分別梳理一下
- 宜城
當我們在蜀中的時候，記錄下來蜀中 宜城的最近距離是5，途經 蜀中->宜城。
現在發現從佳城也可以到宜城，但是距離是蜀中與佳城的最近距離加佳城 宜城之間的距離，即4+4=8，剛才是5，現在是8，所以蜀中到宜城的最短距離和路徑不變。
- 冰城
我們之前還沒有記錄過冰城的相關資訊，所以直接記下蜀中到冰城的途徑為 蜀中 ->佳城->冰城，距離為蜀中與佳城的最近距離加佳城與冰城的距離，即4+5=9。
紅色代表已去過城市
然後，我們再走一步看一步。
此時，我們再挑一個我們沒有去過並且距離蜀中最近的城市，上圖所示，此次我們要去宜城。
到達宜城之後，我們又看一步，發現宜城相鄰的並且沒有去過的城市只有鼎城。
那比較簡單，直接記錄下蜀中到鼎城的最近距離和路徑。
好的，到了這一步夫人可知如何進行下一步嗎？”
“我知道啊，自然還是 走一步 ，可以當前冰城和鼎城距離都是9，我們該去哪座城市呢？”
“好問題，既然距離一樣，那我們隨機去哪一個都行。讓我想一下，夫人冰雪聰明，那我們就去冰城吧”。
夫人嬌嗔到：”相公又拿我打岔，我們先干正事吧！”
我笑到：”來，我們接著走。此時我們到了冰城，又 看一步，即發現冰城相鄰的並且沒有去過的城市只有子城。
所以如下圖所示
此時我們再次選擇距離蜀中最近並且沒有去過的城市，為鼎城。
到達鼎城之後，相鄰的並且沒有去過的城市只有長安，也就是我們的最終目的地。
夫人嘆道：”真不容易啊，我們終於到了長安了！”
我：”慢，從路徑圖中我們看到子城我們還沒有去，而且從這個城市到長安的路徑可能更近。我們來看。
這次我們距離蜀中最近並且沒有去過的城市，即子城，到達子城之後，發現相鄰的並且沒有去過的城市只有長安，並且計算出來從子城到長安的距離為12+2=14，小於從鼎城到長安的距離16，所以需要更新長安的最短距離為14，並記下
走到此時，我們還按照之前方法走的話，發現距離蜀中最近並且沒有去的城市只有長安了。等到了長安，發現已無剩餘城市可去。
此時，我們的結果也呼之欲出。”
夫人在旁邊開心的跳了起來，我也長嘆了一口氣，實際情況雖比圖中描述複雜很多，但最起碼有了路子可以尋到最短路徑了。
此時東方既白，雞鳴響起，我推開門，朝陽如鮮花綻放，如水波四散。
我站在院里，望向遠方，好像看見了長安。
創過業，賠過錢。遂轉行，程式設計師。
從外包，到大廠。寫程式碼，寫文章。
胡思亂想，文章沙雕。
歡迎關注，與君同好。
