6.4 选择题：算法适用条件

先按任务选择算法：MST覆盖所有点且总边权最小；最短路优化一条或多条路径；拓扑处理依赖；关键路径处理工期。Dijkstra只接受非负权，Floyd全源，BFS等权。

手工状态

一个MST中两点间路径不一定是原图最短路径。反之最短路径树虽从源到各点最短，总权也不一定最小。

结构与代码

多选：A Kruskal可用并查集判环；B Dijkstra可处理负边；C Floyd外层是中间点k；D DAG一定至少有一个0入度点。答案A、C、D。

正确性依据

算法正确性来自各自不变量和条件；条件不满足时不能用样例恰好正确代替证明。

错解反馈

把MST和最短路树等同；拓扑输出V个之前就断言无环；关键活动等同最长单边。

迁移训练

稠密图全源最短路且无负环，常选什么？答案Floyd，O(V³)并能处理负边。