[爆卦] 清華大學突破Dijkstra演算法瓶頸

[jackliao1990 (j)]

https://arxiv.org/pdf/2504.17033

Dijkstra演算法是找網路中每個點的最短路徑時的最經典算法(資工系必學)
自1956年來科學家們遭遇了理論瓶頸:如果想設計解決最短路徑問題的最快算法
需先找到距離起點最近的點
這需要按距離排序這些點
這導致演算法速度無法快過排序所需時間

在斬獲理論計算機國際頂級會議STOC 2025最佳論文獎的作品中
北京清華學者發布不依賴排序的新演算法
打破持續數十年Dijkstra演算法理論瓶頸
他們用貝爾曼-福特演算法定位關鍵節點後優先探索
接著回溯處理其他邊界節點
由於不嚴格按距離順序探索每層節點
排序障礙自然失效
若採用恰當分層策略
其速度略超優化版Dijkstra演算法
新演算法運作效率已遠超現有理論極限
任何依賴大量最短路徑運算的系統都將受益
這將為資料中心節省大量CPU運算資源

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.253.168.210 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Gossiping/M.1754908560.A.F0A.html
推 royroy666: 跟我想的一樣
→ johnhmj: 所以欸哎要做出來了嗎？
推 ko7625: 可惡 被搶先了 算他們厲害突破我的盲點
推 SUMPO: 小學科展等級
→ arnold3: 清大挺厲害的
→ t81511270: 這個課本級 經典演算法 被破了嗎 好猛
推 AgentSkye56: 有台灣清大賺的錢多嗎
推 Ilat: 欸我小學的科展484被搜出來了
推 MeeToo: 大家準備重修演算法
推 shokotan: 實際應用會快到飛起來嗎
推 t81511270: 聽起來像骰骰子ㄇ 骰的好 就比較快
噓 oftisa: 中華民國清華大學排名低 根本做不出來
推 adios881: 哈這個我專業 不如來問我
推 fishouse: 所以曹捐的1500跑去哪了？
推 XDDDDDDDDDD: 之前不是也有突破 hash 結果沒有
推 guolong: 台灣的清華只會賣雞雞
噓 touurtn: 北京清大==
→ tank44444: 確定嗎
→ adios881: 這個板會正確唸dijkstraㄉ應該沒有10位
噓 SRNOB: 有台灣清華賺錢嘛? 只要用手機拍照買豪宅
推 abcdragon: 不是臺灣清大，臺清大只能出tsmc間諜
推 whitenoise: 為啥要先丟arXiv？？
推 m06800825: 追斯挫algorithm
推 justice0616: 是北京不是新竹 勿高潮
推 y30048: 我都唸IKEA
→ m06800825: 現在論文都會先丟arxiv搶先曝光吧
推 believefate: 當間諜賺比這更多錢 傻傻的
噓 b0000000000: Sparse graphs
推 scitamehtam: 清大屌打台大交大了
推 iamandre: 中國的科技會在二十一世紀統治全球
→ iamandre: 這是注定的
→ kidd085: 我文組不懂 可以解釋嗎==
→ AoWsL: 對面的
推 vzerov: 真的台灣國中科展程度而已
推 lianginptt: 新演算法要叫什麼？感覺阿共仔現在雖
→ lianginptt: 說突破很多，但是好像都沒有喊出什麼
推 scitamehtam: 隔壁交大怎麼那麼廢…
→ lianginptt: 招式名稱的樣子？
推 chao0210: 這好久惹
推 scitamehtam: 明年清大資工分數即將超車台大電機
→ scitamehtam: 了嗎？
推 qwe04687: 前幾天有看到
→ pojohn: 最短路徑就是一個貨車司機送貨到一百個站
推 Ceferino: 青鳥：台灣之光！Team Taiwan 怎麼輸
推 kotorichan: 北京清華大學 正牌清華很強
→ pojohn: 走那些路徑可以最快送完,路徑的組合很多
→ pojohn: 每個路徑都算過一次可能要幾年或幾百年
推 intointo: 北京清華
→ pojohn: 演算法就是來幫你求取一個相對最佳的解
推 palapalanhu: 台灣的只會大罷免
推 g10: 最短路徑 不錯不錯 怪不得可以買豪宅
→ pojohn: 這類問題很適合量子電腦來跑
推 sleepy5566: 哇喔 教科書要更新了嗎
推 depo: 這不是我高中科展的東西嗎
推 mecca: 這在台灣大概是國中科展等級
推 ambitious: 這樣跑ptt回快一點嗎
推 sdf90258: 北京清大
推 keyneslan: 以為是台灣清華…
→ ornv: 果然跟我計算的方式一樣
推 scitamehtam: 明年清大資工分數超車台大電機
推 limeazure: 這個在科展最多第三名
推 scitamehtam: 交大電資不是很秋條？ 被隔壁兄弟海
→ scitamehtam: 扁了
推 marke18: XD
推 hizuki: 偽清大還是國立清大？
→ jack529: 厲害
推 scitamehtam: 台大電機不是號稱超強？被小清大虐
→ scitamehtam: ？
推 amethystboy: 值得鼓勵
推 DirtyVegas: 聽起來像是矇的  剛好中就特別快？
推 Tenging: 新的間諜
→ ringil: 原來是北京清華…
推 turndown4wat: 講中文好嗎
推 hamnett17th: 中國真的要崛起了
推 appleball200: 推
噓 b9021008:  肛!
推 LeoYuri: 幹好屌啊
推 jason90814: 北京清華的名字就只有清華大學沒錯
→ jason90814: 台灣的叫國立清華大學
推 DeRozan5341: 以前考試還要考手算
→ s51007john: 這個算法怎麼看起來像亂碼
推 imnaruto: 反觀台灣清華XD
推 nashpan7: 牛人
推 Hirano: 嗯嗯跟我想的一樣
推 lia910229: 台灣清華比較猛吧，幫日本突破二奈
→ lia910229: 米研發誒
推 fly0204: 跟鬼一樣
→ WaineLee: 請注意 是北京的 所以一定假的
→ walinama: .... 還以為是優化Dijkstra....
推 mo42: 可以讓AI學會就好嗎 我演算法不想重修
推 deray: 跟我國小想的差不多 但是沒發表
推 mikiji: 跟我想的一樣
推 scitamehtam: 清大超秋條，台大電機加油好嗎？
推 justhit666: 感覺好像蠻屌的欸
推 henry4204aaa: 以後課本會改嗎
推 ericdragonw: 所以Dijkstra到底要怎麼念
推 snooopy: 可惡 我先想到的
噓 agoodjob: 交大生表示：請問研究所要選交大還台大
推 jknm0510a: 恭喜以後的資工系演算法多學一個
→ sushi11: 清台交成
推 offstage: 等等，這不是我20年前大一計概第一次作
→ offstage: 業嗎
推 phoenix1005: 終於
推 iamgyfan: 天啊
推 sses60802: 嗯 跟我想的一樣
推 scitamehtam: 這題真的強炸，明年清大資工超車台
→ makki: 還以為是台灣的清大
→ scitamehtam: 大電機了吧…
推 p2p8ppp: 怎麼知道是關鍵節點==
推 scitamehtam: 好奇台大電機是只會考試而已嗎？
→ scitamehtam: 台大電機成績高清大資工不少哎
→ scitamehtam: 結果這等級難題確是清大解出來？
→ tttkkk: What is the trade-off?
推 orange0319: 有ai之後，感覺科技突破速度都變快了
推 Fukker: 台灣清大專出廖北啊
→ Fukker: 對的起庚子賠款嗎？
推 afu4869: 演算法課本會再變厚嗎? QAQ
推 zsp8084: 不如台灣國小科展
推 rswa: wow 這突破也太強大了
推 Mashiro17: 好厲害！
推 Rhapsody: 比國中小科展好懂
推 k078787878: 好扯
推 abc22753939: 就是這個 大學的時候教授在台上一邊
→ abc22753939: 講 我就在座位下一邊思考這個
推 gk1329: 中國又贏
→ pikinini: 學理上，這對已有量子電腦的時代來說，
→ pikinini: 可能不是很稀奇；說開始放到學術和實務
→ pikinini: 上來進步優化還比較恰當。
推 wmtsung: 要把技術送給日本了嗎？
→ wmtsung: 阿原來是北京清華
推 joywilliamjo: 雖然說是稀疏圖的話效能會輸dijkstr
→ joywilliamjo: a，但現在東西都那麼多node跟路徑，
→ joywilliamjo: 超屌
推 adsl9527: ok 演算法又要學一個
推 jily: 嗯嗯 跟我想的一樣 >//<
推 bybyduz: 不過bellman ford複雜度是O(VE),E多的話
→ bybyduz: ，結果也是變好嗎？
推 pmes9866: 牛逼
推 iamflash: 跟我想的一樣
推 dazzzlee: 有屁用 台灣清大拍拍照就有豪宅屌多了
推 Cactusman: 嗯嗯跟我想得一樣
推 yiche: 膜拜神人Orz
推 LoveLena5566: 所以看起來是改良Bellman-Ford，效
→ LoveLena5566: 率可以優於Dijkstra
推 billabcddog: 台灣繼續搞大罷免，連車尾燈都看不到
噓 AniOAO: 北京清大
推 abyss5566: 台灣清大突破台積電資安
推 tanchuchan: 跟我的科展題目差一點點
推 iksion: 我覺得清大生突破台積漏洞盜資料比較屌
推 gary82gary: 怎麼找關鍵節點？如果每個都走最佳路
→ gary82gary: 徑不就會造成頻寬瓶頸？
→ l40112: 還是輸給高中生科展
推 ifconfig5566: 真的假的阿
推 Jason8051: link-state的protocol要重寫了嗎
→ orton417: 其實跟我想的差不多
推 KingIphis: 果然是北京清華
噓 NEX4036: 中又贏 贏兩次 贏麻了
推 RockCat0218: 被搶先發表了..
→ johnship: 還有幾集可以逃？
→ dsf980036: 強
推 raysbuck: Van Dijk stra
推 hope2801: 反觀臺灣的清華
→ hope2801: 只會偷東西
推 internetms52: 呃…這省略的部分太多惹吧
推 dogalan: 結果是北京清華...
推 ncuephysics: 俎国以後不需要先進的cpu
推 BJC4100: 至少我們清大還有內賊
推 sufferlove: 這只能膜拜了。