迪杰斯特拉是什么(最短路径算法3分钟就搞懂)

今儿个本来想自己搞个导航小工具来着，结果让“最短路径”这玩意儿卡了大半天，真够恼火的！

我一开始想的太美了

脑子一热寻思这有啥难？不就找条最近的路嘛自己捣鼓个数组来回折腾一下应该就行了。结果吭哧吭哧写了半天代码，乱七八糟的，一跑起来：

气得我差点把键盘拍桌子上。这破玩意儿根本不能实际用！

实在没辙了，灰溜溜去搜“咋样能快点儿找最短路径”。哗一下子出来一堆听着就头大的词儿，什么A、贝尔曼-福特，还有个名字挺拗口的——迪杰斯特拉（Dijkstra）。说实话我连这名儿都念不顺溜，当时就想直接关网页躺平算了。啥权重松弛，看着跟天书似的。

正烦着，刚好瞅见以前学计算机那哥们在线，赶紧抓住他嚎了一嗓子：“救命！这迪啥斯特拉到底是个！”这兄弟笑疯了：“老铁你这脑子是堵住了？这算法说白了你天天在用，点外卖看配送时间的时候APP搁后台算的不就是它！”

骂归骂，他好歹给我画了个图讲明白了。我赶紧按他说的方法自己比划了一遍：

第一步，把我家定成起点（距离=0）。其他那些地儿，奶茶店、烧烤摊，默认都当成远在天边（距离=无穷大）。

第二步，抓起点开始干活。瞅瞅从我家直接能奔哪儿去——能去地铁站（耗时15分钟），能去公交站（10分钟）。那行，暂时最短距离就这么记着。

第三步，找个目前耗时最少的地儿接着搞。公交站只要10分钟？行，就它了！接着看从公交站发散出去：到烧烤摊15分钟，到公司大楼25分钟。

注意了！关键来了：从我家总耗时要这么算：去公交站10分钟，加上从公交站到烧烤摊的15分钟，总共才25分钟！比我之前从家瞎绕可能快多了！赶紧更新记录。

第四步，这么一遍遍重复：逮住当前离起点最近（耗时最短）的地儿，往外扩散更新邻居的耗时。谁家有更快的路就更新谁，没更快的就拉倒。

困得眼皮打架，但脑子突然“叮”一声开窍了：这玩意儿就跟咱玩扫雷似的，一点点往外摸安全区域！它聪明就聪明在每次都死磕最近的点，保证最短距离不返工。我吭哧哧写的那个笨蛋代码可不就是在所有路上瞎撞吗？怪不得慢成狗！

整了个简单版代码跑地图数据，还真能三分钟内给我算清从家到公司哪条路等红绿灯最少！折腾这大半天，总算搞明白这迪杰斯特拉原来就是稳扎稳打、“从近到远步步为营”的找路法子。这破算法要是早点儿学透，省我仨钟头打游戏多香！