迷宮尋路 - Shortest Path ← 返回遊戲列表
演算法:
距離表(從 S 出發)
0
步驟數
0
鬆弛次數
Dijkstra
演算法
起點 S
終點 T
處理中
已確定

最短路徑演算法

Dijkstra:貪心策略,每次選距離最小的未處理節點。O((V+E) log V),不支援負權邊。

Bellman-Ford:動態規劃,執行 V-1 輪鬆弛。O(VE),支援負權邊,可偵測負環。

鬆弛 (Relaxation):若 dist[u] + w(u,v) < dist[v],更新 dist[v]