图最短路径算法
一句话总结
- Dijkstra 算法 和 A* 算法 是 BFS 的拓展，处理不包含负权重的单源最短路径问题
- SPFA 算法（基于队列的 Bellman-Ford 算法）是 BFS 的拓展，可处理包含负权重的单源最短路径问题
- Floyd 算法 是 动态规划 的应用，处理多源最短路径问题
最短路径问题分类
单源最短路径
从某个起点出发，到其他所有顶点的最短路径。
- 输出：一维数组
distTo，distTo[i]表示从起点到节点i的最短路径长度 - 代表算法：
- Dijkstra 算法：BFS + 贪心思想，效率高，不能处理负权重
- Bellman-Ford 算法（SPFA）：BFS 拓展，可处理负权重，效率较低
点对点最短路径
从起点 src 到目标节点 dst 的最短路径。
- 可视为单源最短路径的特例
- A* 算法：启发式搜索，利用终点信息有方向性地搜索
- 关键：启发函数（Heuristic Function）平衡经验法则与实际情况
- 属于启发式搜索算法（Heuristic Search Algorithm）
多源最短路径
任意两节点之间的最短路径。
- 输出：二维数组
dist，dist[i][j]表示从节点i到节点j的最短路径长度 - Floyd 算法：本质是动态规划
- 理论上多次调用单源最短路径算法也可解决
负权重边的影响
| 算法 | 能否处理负权重 | 备注 |
|---|---|---|
| Dijkstra | ❌ | 贪心思想依赖"路径越长权重越大"的假设 |
| A* | ❌ | 同 Dijkstra |
| Bellman-Ford / SPFA | ✅ | 可检测负权重环 |
| Floyd | ✅ | 可处理负权重 |
负权重环：若存在负权重环，最短路径问题无意义（可无限转圈使路径权重无限减小）
为什么负权重导致 Dijkstra 失效？
Dijkstra 假设：随着经过的边增加，路径权重和一定增加。负权重边打破这一假设。
举例：
s->a权重 3，s->b权重 4- 若无负权重，
s到a最短路径就是s->a（权重 3） - 若有负权重
b->a = -10，则s->b->a权重和为 -6，比直接路径更小
算法本质关系
图遍历基础
├── BFS → Dijkstra（贪心） → A*（启发式）
├── BFS → Bellman-Ford（队列优化=SPFA）
└── 动态规划 → Floyd
相关概念
相关实体
- labuladong：算法学习平台作者