Skip to content
所有標籤

#shortest-path

2 篇文章

Stanford CS161 Lecture 11:Dijkstra、Bellman–Ford 與鬆弛的兩種秩序

Dijkstra 每次確定最小 estimate,正確性依賴非負 edge weights;Bellman–Ford 不挑 vertex、反覆鬆弛所有 edges,以 O(nm) 換取負權支援並能偵測 source 可達的負環。

Stanford CS161 Lecture 12:用動態規劃重寫 Bellman–Ford 與 Floyd–Warshall

動態規劃先精確定義子問題,再用 optimal substructure 寫 recurrence,最後依相依順序填表;Bellman–Ford 以 edge 數分層,Floyd–Warshall 則以允許的中繼頂點分層。