【科学】Dijkstra算法再被证明是普遍最优算法 | Edsger Dijkstra | 计算机经典算法 | 单源最短路径 | 堆Heap | 工作集属性 | FOCS 2024最佳论文

[@bestpartners]

谢谢大家指出视频中Dijkstra的发音问题，目前中文网站上有两种翻译，一种是戴克斯特拉，一种是迪杰斯特拉，但是经过相关查证和观众提醒，mathoverflow.net/questions/4381/pronunciation-dijkstra ，确实应该读音为前者 /dike·struh/，特此更正，也向大家真诚的表示歉意，向Dijkstra前辈表示歉意。这也反映出我个人的知识和水平不足，对我也是个很好的教育作用，以后做内容应该要更加谨慎的求证求索。 其实做这个频道快两年，期间有很多视频内容被观众们指出错误之处，很多都是我自己注意不到的细节，真心感谢。如今对我来说，做内容更是一个自我提升的道路和方式，也希望大家以后继续多在评论区指出问题，我一定虚心接受和改正。 再次向大家表示歉意，感谢大家一直以来的支持和包容，我也会继续努力。

[@fordchang926]

我也读迪杰斯特拉。。。

[@zhongzhongclock]

这么长，我们能读的完吗？一看就是用chatGPT写的，对吧？ 我猜你肯定说不是chatGPT写的，对吧？

[@bestpartners]

@@zhongzhongclock 确实亲手写的，还改了两遍。你不信我也没办法，我每天都写几千字的稿子，写个这个道歉信花不了几分钟，还不至于用 AI 来写

[@zhongzhongclock]

@@bestpartners 哈哈哈哈哈！开个玩笑

[@zhongzhongclock]

@@bestpartners 读错了也正常，因为荷兰人名在翻成英文本身就有很多发音对不上或者微小的错翻(因为根本就没那个音)，反正在跨语言交流的时候，大家都不太在意对方叫自己的名字的发音是否准确，只要彼此知道是在叫谁就好了。

[@givensur4982]

对这个名字记忆深刻，因为当时老师说这个名字里连续包含了ijk，所以他很喜欢。算法本身是贪心策略下的动态规划。

[@fordchang926]

这个算法太漂亮了。虽然贪心算法，但是效率真的极高。

[@alegalone]

哈哈哈 知道是最好的就夠了 以後不用費心去優化了

[@zefyra-metriz]

有知識深度，Good Job，我一直都很想研究這算法，對我有幫助

[@yidonghuang3280]

这个是我印象最深的算法 很有趣

[@徐明-m4f]

这个算法太经典了，记忆深刻，铁路算运费的项目里用到过

[@X6U477]

你这个发音可真是让我大开眼界😂荷兰语中”ij”是一个元音，读作”爱”。这个名字翻译成“戴克斯特拉”我觉得比较接近。

[@bestpartners]

多谢指正

[@stevenn380]

以前那个球星Rijckard，最早发音里杰卡尔德，后来才知道是莱卡德。ij实际上是y上面加两点类似ü

[@orderofchaos8680]

这个算法其实有点类似于“枚举法”。枚举“所有的下一步”，然后看看哪个”下一步+已有距离“最短就选哪个。循环这个”枚举“直到终点。保证全局最优需要有个关键的前提就是：每一步走下去只会增加距离，而不会减少。当然这个前提基本上可以满足绝大部分现实场景，所以应用面广泛。由此算法发展的A*算法优化了寻找”下一步“的过程所以更加高效，在游戏领域里应用广泛。 对了，这个方法不需要探索所有的节点，只需要在路径里的”碰到“终点就可以停止了。因为所有的”下一步“都只会增加距离，所以碰到终点以后再探寻其他节点只会增加距离偏离最优解。

[@xiaoyuvax]

就是现状最佳循环递归排序

[@mamaya2000]

當年學習時直觀的感覺我願稱他是大水漫灌式算法，就像用水去淹螞蟻窩，有越快的路徑的節點越早被淹沒😂 A*早些年用HTML5實作過，本質上是犧牲低機率的路線來提升效率，在遊戲上是很實際的，但我印象中在極端情況下A*不一定給最佳解

[@doge7562]

@@xiaoyuvax 總結的非常精準

[@AI-fm2vu]

就是边带权重的bfs

[@陳柏曄-w9y]

@@mamaya2000 HTML 不是程式語言，不可能用 HTML 實作 A* ，你大概是記錯了吧 另外，A* 在任何情況下保證最佳解，除非你在實作上有錯誤

[@張夢萊]

遊戲自動尋徑會用到，不過早期自動尋徑比較像火車站。 他會把玩家從遠端帶到一條主幹道，再從主幹道前往目的地。 這種算法簡單有效，就是苦了地圖製作。 ------------------------------------------------------------------- 原來反對Goto是他提出的喔....Goto在高維度迴圈間跳躍時很好用。

[@吼搭啦-h1u]

帶到主幹的過程中也可能塞車😂

[@xorpop]

塞車就是程式設計師的錯 🤣

[@ethanz3153]

非常棒的一期节目，高质量！

[@YetEthanOnly]

這麼硬的東西你都講，不錯，這確實很重要

[@Spring_IoC]

这期节目好

[@Blue-pd3dv]

最简单的往往也是最优的

[@naitetoris8375]

不一定 可能而已

[@小肥肚]

@@Blue-pd3dv 不一定 需要保證一個問題的最佳解是由子問題的最佳解所構成（optimal substructure)

[@hiucollo2402]

Thank you 大 飛 一口氣看到尾 看完再看 🏆 🏆 🏆 🏆 🏆 ☘ 😄 🌺 🀄 😃 💐 ☕ 🌸 😁 🏵 😀 🧧 🎉 🌺 🎊 🏮 🍀

[@mengmeng4312]

牛逼，以后可以放心用了

[@hychung2333]

棒💯

[@sophiac.700]

图是在quanta上拿的，加个citation比较好

[@huangyingjun4545]

第一次听到这个算法还是在学OSPF😄

[@chao541]

再次说明数学家早就能想到计算机算法 高斯等人搞的计算比较简单只是因为缺乏计算工具而已。突破的只要是算力😂

[@xorpop]

go to只適合完全了解自己程式的設計師使用

[@RedsunsChan]

最討厭就是用這算法的題目 之前刷到一題Graph的題目, 只接受最優解, 然後最優解就是Dijkstra算法, 什麼BFS DFS全部不能當最優解 沒讀沒背根本不可能解到這題, 看到討論區才看到一堆人在投訴 我能在刷一題中等題目的時侯憑空想到這個演算法我就不用刷中等題了🤣

[@uartim]

問題是如何得知這些路徑的值，這些路徑是會變，像交通一樣。 車輛的參與也會增加它的值，就像鄭州往開封😂

[@markchen6549]

誇張的是在咖啡廳，他老婆沒有打斷他思考，讓他沈思了20分鐘

[@bestpartners]

贤妻啊，哈哈

[@zhangxin101]

荷兰计算机科学领域也出了几个世界级大师

[@成李-j4j]

有没有算最远路径的算法呢？

[@bestpartners]

这个的意义在哪呢？代价最高？

[@joshuachen819]

每聽到你念一次「迪傑斯特拉」 我就會忘一次Dijkstra原本該怎麼念 超好笑

[@bestpartners]

出洋相了🤣🤣🤣

[@OP4455OP]

CCNA考試似乎也把RIP、EIGRP路由協定拿掉了，只留Dijkstra算法的OSPF

[@cheungkamwah19632100]

發音準不準並不影響內容, 做好視頻, 比指出發音準不準, 更重要！

[@zhongzhongclock]

互联网上的路由器利用路由表的相互更新，其理论基础就是这个算法，俺以前干过这事儿。

[@YiuMingLai]

路由器的是分佈式算法。

[@zhongzhongclock]

@@YiuMingLai 核心的思想依然是不停的更新达到目标地址的最小代价表，各个路由器彼此之间不停的交换这个路由表的信息，直到彼此没有更新的变动，OSPF就是建立在Dijkstra算法上的，当年我建广域网的时候，对这个实现看的很仔细，感慨那么牛逼的一个互联网络，其实核心却如此的简单。

[@tony_boy11306]

路由表更新不是是bellman ford為基礎嗎

[@zhongzhongclock]

@@tony_boy11306 你说的对！两个算法有一些差别，实践中好像确实用的bellman ford算法，不过在原理上我看不出区别。

[@MusicalPan]

這雖然是最優解但一旦節點和路徑上規模計算量就很可怕。 一般這樣的情況還是會用近似的算法去求值。

[@xorpop]

有分區預先計算的方法，還好

[@Hydrawindforce]

看你的视频总是看完了，没时间点赞就弹广告了，还得退回来点赞

[@orderofchaos8680]

视频说明栏里给的论文貌似与这个算法无关，是不是贴错了？Optimized Sandwich and Topological Structures for Enhanced Haptic Transparency

[@bestpartners]

确实是，少了个最后的数字，谢谢指正🙏

[@黃寶童]

所以 多頭絨泡黏菌 天生自帶被動技能:Dijkstra算法

[@paochu92]

唸dai k stra

[@pingkai]

他这个东西其实很trivial，100个搞计算机的人里面至少有1个人能重新发现这个东西。

[@dereklee1027]

個人覺得影片引入有點太硬了，我是什麼都會看點的人，但影片的"包裝"有種完全看不懂的感覺，令我很疑惑。(因為我覺得沒有什麼事物是真的無法理解的) 個人覺得在開頭盡快帶出"其實是很簡單的概念，就是整理出一套最快找出最短路徑的邏輯"的意思，對行外人的幫助/吸引力會大很多。

[@吳漢-m4p]

为什么，贪心算法不是不一定是最优解吗？

[@9263STYV]

其实这个算法在节点太多以后，感觉还是有点太耗资源。 上万或者百万级别的节点，蚂蚁，黏黏菌以及基因算法会变得特别好用。能在很短的时间和资源下获得一个距离和成本都获得平衡的，可接受的路线，但是不一定是最优解。

[@beichenyang4237]

如果您不在乎理论最优解，而是一个并非最有但也还不错的解，那您说的这三种启发式算法确实更快，毕竟总会设置一个最大iterations，到了这个iteration算法不停都不行。而Dijsktra的时间复杂度是O ( V + E l o g V ) ，节点和边的数量越多所花时间就越多。

[@xiaoyuvax]

不就是循环递归排序吗？说得那么玄。

[@kmkwong]

👍👍👏👏

[@alexyoung3609]

第6✌

[@Lee-sr9el]

作为一个computer scientist竟然一直不会发这个词的音

[@littledesignsolution]

应该翻成戴克斯特拉

[@bestpartners]

是的，我已经自我检讨过了😭

[@chunheikwok6738]

看不太明為何AD節點更長？ 比abcd 更短。端對端不是更快嗎？

[@hongxuanchen]

那个长度不表示远近。那个数字才表示距离

[@xorpop]

這種資料結構示意圖的連線只代表相關性本身，不是代表距離或成本

[@breekysneaky3826]

代克斯特拉

[@モノクロムセレティクス]

每次看这个名字都感觉是作者脸滚键盘打出来的😂

[@skyacaniadev2229]

那完了，这就是上限？

[@NickZhaoable]

穷举法，怎么可能不是最优？

[@steak1314]

没读过大学 只知a*

[@willsonsiao357]

你就告訴我，這和統計學的樹狀圖有何不同，何以要新命名？

[@goldenboy0121]

你個沙雕，tree只是graph的subset，屁都不懂就閉嘴

[@xorpop]

因為那不是樹狀圖，而是至少二隻蜘蛛在互相競爭結網捉食物的動態過程

[@WTF_howareyou]

@@willsonsiao357 heap是一種tree但tree不等於heap

[@scchen2011]

第二

[@icelikingai142]

读作“迪杰克斯特拉”

[@goldenboy0121]

根本沒有杰這個音

[@hongsing3661]

丟可斯欻算法，j是發u的音。因爲dijkstra是荷蘭人，該按荷蘭音讀

[@bestpartners]

谢谢指正

[@uartim]

greedy algorithm

[@skyacaniadev2229]

这个更快但是不一定找到最佳路线吧😂

[@xorpop]

這個適合已知的格式化模型快速尋徑

[@ouyangfeng6911]

😂一直都在学算法，就是从来没有学明白

[@TWALBEVA]

明年拿諾貝爾和平獎😂