圖的最短路徑~~~《碼農也穿越》第一集
- 2021 年 3 月 16 日
- 筆記
本集簡介
我本一介小碼農，整日耕於代碼中。
一覺醒來竟穿越，略施算法得聖寵。
一
每日的生活就好像一遍遍for循環，上班，開會，撕逼，加班，摸魚，加班摸魚。
好在，最近可以看《贅婿》，把我從千篇一律的生活中拯救出來。
又是一個周日的晚上，看着主人公在古代入贅豪門，廣開分鋪，結識丞相，不禁感慨我要是能穿越就好了，可是一個程序員穿越回去可以幹什麼呢？
鬱悶之下開了一瓶啤酒，邊胡思亂想邊追劇，不勝酒力的我就這麼迷迷糊糊睡著了。
不知道過了多久，我耳邊聽見有人在喊：”大人大人，皇上有急事招您！”
我驚醒一看，周圍已不是我出租屋的裝飾，而且立着漢白玉的柱子，四周的牆壁也全是白色石磚雕砌而成。
我一把拿過床邊的鏡子，鏡子中的人留着長發，貌比潘安，散發著一股年少有為不自卑的氣質，一掃往日一副鬱郁不得志狀態。
我竟然真的穿越了！
二
為了保證穿越之後的儀式感，我還是打了自己兩巴掌，沒有問題！
門外的僕人越發著急，我忙說起來了起來了，心想我都位高權重了咋剛起床就得上班。
僕人直接進來幫我換好衣服，並說高公公在外面等候多時了。
在高公公的帶領之下，我們坐上馬車直奔皇宮。
擔心言多必失，我全程不發一言。但是依然按捺不住我激動的心情，這次投胎我給自己打個滿分。
很快到了皇宮，高公公帶着我一路小跑，直奔皇上書房。
行過電視劇看過的大禮之後，皇上滿臉愁容，嘆氣道；”愛卿啊，貴妃整日鬱鬱寡歡，問起原因，是因為思念家鄉的荔枝了，可蜀中到長安數千里，中間涉及了幾百條官道，途經幾百個驛站，繞來繞去，送到時荔枝都已腐爛。愛卿可有什麼法子，來找出蜀中到長安的最近道路啊。”
我一聽，這不是我的老本行嗎，無向圖的最短路徑啊！
我當時恨不得表演一下宣紙毛筆寫算法的祖傳手藝，可一尋思，皇帝也看不懂代碼，搞不好以為我在鬼畫符。
算了，能和皇帝講清楚就行了。
於是我上前一步：”臣有一計，按此計可尋得最短路徑，定可讓貴妃吃上鮮美荔枝。”
皇上大喜：”筆墨伺候，讓愛卿給朕道來。”
我在紙上畫到
皇上請看，我們可以類比於從0點到4點的最短距離。
算法很簡單，用三個變量，重複走三步，即可得到最終結果。
三個變量
sptSet(shortest path tree set) 數組
創建一個數組sptSet，用來記錄最短路徑中包含的頂點，也就是哪個頂點計算出來到源點的最近距離了，就把它加進去。
最初，此集合為空。
distance數組
創建一個數組記錄每個頂點到源點的距離，當然最開始為INFINITE（無限大）。
同時將源頂點的距離值指定為0。
parent數組
這個是當我們更新
distance數組的時候，記錄該節點的上一個節點，好記錄整個最短路徑所通過的節點。
三步走
-
選出一個不在
sptSet數組並且distance數組中之最小的節點，該節點我們可以稱之為u。
當然，第一次就是選擇源節點0。 -
把
u放到sptSet數組中。 -
遍歷
u所有相鄰的頂點，如果相鄰頂點i的距離值(即distance[i]的值）大於u的距離值加上u到該相鄰頂點的距離之和S，我們更新相鄰頂點的距離值為S。
同時，修改parent數組，即parent[i]=u。
如此重複下去，直到我們遍歷完全部節點，就可以獲取源點到每一個節點的最短路徑。
當然，從蜀中到長安的最短路徑也知曉了。”
皇上一臉茫然的看着我，我才意識到，我已經穿越了，這樣講皇上肯定聽不懂，就是看這個文章的現代人都不一定能懂。
不如一步步推導，皇上肯定更加清晰。
我又說道:”皇上，來我們實際走一遍，您便一目了然。”
數組
sptSet最初為空，distance為{0，INF，INF，INF，INF，INF，INF，INF}，其中INF表示無窮大。 現在選擇距離最小的頂點，也就是選擇頂點0，將其包含在sptSet中。
因此，sptSet變為{0}。 將0包含到sptSet之後(圖中變綠節點)，更新其相鄰頂點的距離值。
0的相鄰頂點是1和7，1和7的距離值更新為4和8。
同時修改parent數組
parent[1] = 0
parent[7]=0
選擇當前具有最小距離值且尚未包含在sptSet中的頂點，這次選擇了頂點1並將其添加到sptSet。 因此，sptSet現在變為{0，1}。
更新相鄰頂點的距離值，因此頂點2的距離值變為12。
同時修改
parent[2]=1
依然選擇具有最小距離值且尚未包含在sptSet中的頂點，這次選擇了頂點7。 因此，sptSet現在變為{0，1，7}。 更新頂點7相鄰節點的距離值，即修改頂點6和8的距離值為15和9。
同時修改
parent[6]=7
parent[8]=7
我們如此重複，直到遍歷全部節點。
皇上，我給您寫個代碼，您立馬就知道怎麼回事了！”。
此時皇帝更加迷惑了，趕緊搖了搖頭，說:”愛卿，你就說需要多少學士，計算多久能出結果吧。”
我恍惚間覺得自己好像在被產品催問什麼時候能上線，立馬答道，只需十名學士，三日必可出結果。
皇上頓時開龍心大悅，許諾此事若成必重重封賞，我一想到剛穿越就能立功，三跪九拜退出書房。
三
數日之後，我已算得從蜀中到長安的最短路徑，鮮美荔枝也一擔擔運往皇宮之中。
一日無事，我站在宮外高樓之上看着騎士背着荔枝馳入皇宮，不僅感嘆自己之前雖是碼農，在社會上地位不如醫生老師之輩，穿越之後竟也能如魚得水，活得如此滋潤。
此時突然聽到旁邊一位老先生嘆氣到： 皇上荒淫無度，百姓民不聊生，這日子何時是個頭啊。
我湊過去，問道：”老先生，可有心事？”
老先生搖了搖頭，轉身在紙上作詩一首：
長安回望綉成堆，山頂千門次第開。
一騎紅塵妃子笑，無人知是荔枝來。
寫罷便拂袖而去。
望着老先生遠去的身影，我突然意識到，自己也要做點什麼，來改變這個朝代了。
未完待續。。。。。。
友情提示，關注公眾號可提前觀看下一集哦！
創過業，賠過錢。遂轉行，程序員。
從外包，到大廠。寫代碼，寫文章。
胡思亂想，文章沙雕。
歡迎關注，與君同好。
