第6章笔记：最短路与最小生成树

目标

区分路径最优和连通成本最优，掌握松弛与安全边证明。

七课依赖

• 松弛与最短路上界：围绕松弛与最短路上界先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：Dijkstra禁止负边；MST不是最短路径树；溢出会破坏松弛比较。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
• Dijkstra与堆优化：围绕Dijkstra与堆优化先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：Dijkstra禁止负边；MST不是最短路径树；溢出会破坏松弛比较。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
• Bellman-Ford与负环：围绕Bellman-Ford与负环先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：Dijkstra禁止负边；MST不是最短路径树；溢出会破坏松弛比较。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
• Floyd与全源最短路：围绕Floyd与全源最短路先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：Dijkstra禁止负边；MST不是最短路径树；溢出会破坏松弛比较。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
• Kruskal与割性质：围绕Kruskal与割性质先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：Dijkstra禁止负边；MST不是最短路径树；溢出会破坏松弛比较。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
• Prim与跨割最轻边：围绕Prim与跨割最轻边先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：Dijkstra禁止负边；MST不是最短路径树；溢出会破坏松弛比较。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
• 最短路和MST的反例对照：围绕最短路和MST的反例对照先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度；边界：Dijkstra禁止负边；MST不是最短路径树；溢出会破坏松弛比较。 本课必须再检查边界输入、整数溢出、下标和不可行状态。

复杂度与适用条件表

算法对象	不变量/复杂度来源	使用边界
松弛与最短路上界	围绕松弛与最短路上界先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	Dijkstra禁止负边；MST不是最短路径树；溢出会破坏松弛比较。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
Dijkstra与堆优化	围绕Dijkstra与堆优化先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	Dijkstra禁止负边；MST不是最短路径树；溢出会破坏松弛比较。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
Bellman-Ford与负环	围绕Bellman-Ford与负环先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	Dijkstra禁止负边；MST不是最短路径树；溢出会破坏松弛比较。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
Floyd与全源最短路	围绕Floyd与全源最短路先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	Dijkstra禁止负边；MST不是最短路径树；溢出会破坏松弛比较。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
Kruskal与割性质	围绕Kruskal与割性质先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	Dijkstra禁止负边；MST不是最短路径树；溢出会破坏松弛比较。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
Prim与跨割最轻边	围绕Prim与跨割最轻边先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	Dijkstra禁止负边；MST不是最短路径树；溢出会破坏松弛比较。 本课必须再检查边界输入、整数溢出、下标和不可行状态。
最短路和MST的反例对照	围绕最短路和MST的反例对照先写朴素算法，再提炼状态或不变量，证明优化保持答案并计算时间空间复杂度	Dijkstra禁止负边；MST不是最短路径树；溢出会破坏松弛比较。 本课必须再检查边界输入、整数溢出、下标和不可行状态。

复盘

每题保存暴力、优化、证明、四组边界测试和首个WA输入；一周后换数据重做。