6.4.2 BFS、Dijkstra 与 Floyd 最短路

BFS适用于无权或等权边；Dijkstra求单源非负权最短路，每轮确定当前最小暂定距离顶点并松弛出边；Floyd用动态规划求全源，逐个允许中间点 k，更新 d[i][j]=min(d[i][j],d[i][k]+d[k][j])。

手工状态

边0→1权2、0→2权5、1→2权1。Dijkstra初始d=[0,2,5]，先确定1并松弛得d2=3。Floyd在允许1作中间点后也把0→2更新为3。

结构与代码

Dijkstra堆实现 O((V+E)logV)，不能处理负权边；Floyd O(V³)、空间O(V²)，可处理负边但不能有可达负环。INF相加前必须判可达，防溢出。

正确性依据

松弛保持每个距离是某条实际路径长度；Dijkstra依赖非负权保证最小未确定距离不会再改善；Floyd第k轮正确表示中间点只取前k个的最短路。

错解反馈

Dijkstra遇负权仍使用；Floyd更新顺序把k放最内层；无边INF直接相加溢出。

迁移训练

边0→1=4,0→2=10,1→2=-6应选什么算法？答案不能用Dijkstra；可用Bellman-Ford，若全源也可Floyd且检查负环。