最短路径

两个算法各自解决什么

• Dijkstra：单源、边权非负。每次选未确定的最短距离结点，松弛它的邻居。
• Floyd：多源、允许负权边（但不能有负权回路）。本质是三重循环的动态规划。

复杂度对照

算法	时间复杂度	适合的图
Dijkstra（邻接矩阵）	O(n²)	稠密图
Dijkstra（堆优化）	O(m log n)	稀疏图
Floyd	O(n³)	求任意两点

手算提醒

1. Dijkstra 每轮只确定一个结点，写出每轮的 dist 表能拿过程分
2. Floyd 的 k 必须在最外层循环——写反了结果就是错的
3. 负权边出现时，Dijkstra 直接失效，不要试图「修正」它

一句话记忆

非负单源用 Dijkstra，多源随便用 Floyd，有负权回路的图最短路径没有定义。