CSCI2100 · 定義 · 第 14 章 · 圖算法
鬆弛
下面有 0 層前置知識
在 Dijkstra 算法中,dist[v] 是已發現的由源點到 v 的最短路徑長度;鬆弛邊 (u, v) 指當 dist[u] + w(u, v) 嚴格較小時更新 dist[v] 及 v 的父頂點,而定案使頂點的標籤成為最終值。
出現在
- 14.2 加權圖的前沿:Dijkstra 與 Prim · 首次引入
前置知識
筆記中沒有比它更基礎的知識點,它是起點。
後續知識
「可能的根源」和複習路徑需要你在這些知識點上的作答紀錄。目前沒有紀錄,所以不作任何建議。
一直追溯到起點的最長鏈
它下面沒有記錄任何知識點:它是起點。