CSCI2100 · 定义 · 第 14 章 · 图算法
松弛
下面有 0 层前置知识
在 Dijkstra 算法中,dist[v] 是已发现的从源点到 v 的最短路径长度;松弛边 (u, v) 指当 dist[u] + w(u, v) 严格更小时更新 dist[v] 及 v 的父顶点,而定案使顶点的标签成为最终值。
出现在
- 14.2 加权图的前沿:Dijkstra 与 Prim · 首次引入
前置知识
笔记中没有比它更基础的知识点,它是起点。
后续知识
“可能的根源”和复习路径需要你在这些知识点上的作答记录。目前没有记录,所以不作任何建议。
一直追溯到起点的最长链
它下面没有记录任何知识点:它是起点。