這就是算法! 【Dijkstra算法】送外賣如何用算法抄近道

神奇的科普
12粉絲
7 次觀看·2026年3月30日
AI 生成·可能包含錯誤
中午12點 烈日當空
張三正在兼職跑外賣
您有新的外賣訂單 請及時處理
張三打開一看
新來了4個訂單
地址竟然指向同一個地方
迪結斯特拉鎮
外賣群裏早有傳聞
這個小鎮位置偏僻
在導航軟件上幾乎沒有信息
進了這個鎮就別想找着北
後面訂單都得超時
鎮上似乎人家三天兩頭點外賣
騎手們都避之不及
但訂單總得有人送
這燙手的山芋輪到張三了
我不是地獄 誰入地獄
好歹咱也是學計算機的
那麼多算法可不能白學
他的程序打包好4份外賣
馬不停蹄的趕往小鎮
到了村口歪脖子處
眼前是一片坑窪不平
曲折蜿蜒的泥土小路
4份訂單的收件人分別是
唐三 尊武 豬八和沙四
張三想
既然以後可能還得來送
不如今天就把整個路線摸清楚
要進小鎮就必須先經過村口
如何才能從村口最快送到每一家呢
他腦中靈光一閃
這不就是最短路徑問題嗎
數據結構可悟
圖論那一張講過
張三開始畫草稿圖
起點是村口
其餘四戶人家是目的地
從村口出發有兩條已知路線
到唐三所在的東土大院
需騎行5分鐘
到孫武所在的花谷小區
需騎行7分鐘
問題來了
先送誰的
唐三吧
時間更短
而且說不定能打聽到
通往其他家的捷徑
騎上電驢
張三一路拐拐繞繞
終於抵達東土大院
您好 您的外賣到了
開門的是個和藹的禿頂中年男人
正是唐三
唐叔
您知道孫武和豬八家怎麼走嗎
孫武住在花谷小區
往南騎2分鐘就到豬八嘛
在高老莊往東騎6分鐘
他算了下
村口 唐三 豬八11分鐘
村口 唐三 孫武7分鐘
與我直接去孫武家一樣長
他現象5個點分成了兩波
村口和唐三家是去過的
其餘都是沒去過的
從沒去過的中
又要選擇一個路徑最短的新點去訪問
也就是孫武家
每到一個新點就能知道
從這個點到其他沒去過的路徑
然後計算新的用時
如果比之前短就更新最短路徑
到了花谷小區樹蔭下
一個體毛旺盛的小夥
正坐在石凳上啃桃子
孫武的外賣到了
俺就是老孫 給我吧
你是新來的吧
豬八姐家往東北騎3分鐘就到了
沙四家可也要往東騎10分鐘
張三連忙道謝
沙四家終於有了眉目
村口 孫武 沙四17分鐘
豬八家有了更短的路徑
村口 孫武 豬八
總共10分鐘更新最短路徑
這就是鬆弛操作
當你找到一條通往某個點的新路徑時
要比較它和之前已知路徑哪個更短
然後更新最短路徑值
緊接着他來到豬八家門前
門前一個膀大腰圓的女人
正哼着小曲擦玻璃
張三送上外賣後問起沙四家
他笑着說
就在流沙溪邊上
往南騎3分鐘就到
村口 孫武 豬八 沙四
13分鐘比之前17分鐘更優
再更新
他沿着小溪找到沙四家
老沙的外賣
放門口石桌上就行
一個紅髮大漢正蹲在院子裏
磨扁擔頭也不抬的喊道
做完最後一單
他打開草圖
又重新梳理了一遍思路
這不就是單元最短路徑問題嗎
而他剛剛完成的
其實就是這套算法的全過程
把所有點分成已訪問和未訪問兩類
每次從已訪問點出發
挑出一條當前最短的路徑
連接到未訪問的點
看看是否能通過它
更新去其他點的最短距離
重複這一過程
直到所有點都被訪問過
張三感悟到
在生活裏跑一次算法
或許比做十道作業題都有意義
晚上回家
張三把這張手繪
集結斯特拉小鎮路線圖
發到了騎手群裏
地圖上還標好了
從村口到每戶人家的
最短路徑和所需時間
有老騎手驚歎
你小子是去鎮上跑了十幾回
才畫出來的吧
張三得意地回答
我今兒個頭一回去
怎麼可能
你是用什麼祕訣
快教教我們
這其實是一個算法
但原名叫啥
我也記不清了
既然是在
集結斯特拉鎮想出來的
那就叫它
集結斯特拉算法
張師傅
你送外面之前
是做啥工作的
張三回答
我只是個
計算機專業的
大學生
我是圖靈宇宙
講有溫度的故事
做有色老科
我們下期再見
