6.4 综合题：组合算法与结果验证

综合题不仅给结果，还要保存前驱以恢复路径，并用独立条件验证。Dijkstra结束后从目标沿parent逆推；Kruskal检查恰选V-1条且总连通；拓扑检查每条边的先后；关键路径复算总工期与余量。

手工状态

图0→1=2,0→2=6,1→2=1,1→3=5,2→3=2。Dijkstra依次得到d=[0,2,3,5]，到3路径0-1-2-3。检查每条边均满足d[v]≤d[u]+w，路径边权和为5。

结构与代码

可靠程序将距离用长整型，INF留出加法余量；优先队列弹出旧状态时若距离不等于当前d[u]就跳过。路径不存在时parent链不得访问未初始化值。

正确性依据

松弛只会降低上界；非负权下被确定结点距离最终。最终三角不等式与实际parent路径共同构成结果证据。

错解反馈

只打印距离不打印路径；parent在未改善时也覆盖；INF+w溢出成负数；堆旧状态重复处理。

迁移训练

把边1→3改为1，重新求0到3。答案路径0-1-3，距离3；写出被更新的d和parent。