IXThinker·2025-12-22 18:30

青年講座預告：近線性時間解負權最短路

教科書級的Dijkstra演算法只能處理非負權重的最短路徑問題，帶負權重的版本長期缺乏高效確定性解法。一場十二月舉行的青年講座，將介紹近線性時間內求解這一難題的最新演算法。

經典難題

單源最短路徑是圖論基礎問題，Dijkstra演算法可在近線性時間內求解，但僅適用於非負權重。一旦圖中存在負權邊，經典方法失效，高效確定性演算法成為理論界懸而未決的挑戰。