最短路径（Shortest Path）
在加权图中，计算两个节点之间权重和最小的路径。
本文中「最短路径」和「最小路径权重和」是等价的。
问题分类
单源最短路径（Single-Source Shortest Path）
从某个起点出发，到其他所有顶点的最短路径。
- 输出：一维数组
distTo，distTo[i]表示从起点到节点i的最短路径长度 - 代表算法：
- Dijkstra算法：BFS + 贪心，不能处理负权重
- Bellman-Ford 算法（SPFA）：BFS 拓展，可处理负权重
点对点最短路径（Point-to-Point Shortest Path）
从起点 src 到目标节点 dst 的最短路径。
- 可视为单源最短路径的特例
- A* 算法：启发式搜索，利用终点信息有方向性地搜索
多源最短路径（All-Pairs Shortest Path）
任意两节点之间的最短路径。
- 输出：二维数组
dist，dist[i][j]表示从节点i到节点j的最短路径长度 - Floyd 算法：本质是动态规划
负权重边的影响
| 算法 | 能否处理负权重 | 原理说明 |
|---|---|---|
| Dijkstra | ❌ | 贪心思想依赖"路径越长权重越大"的假设 |
| A* | ❌ | 同 Dijkstra |
| Bellman-Ford / SPFA | ✅ | 可检测负权重环 |
| Floyd | ✅ | 动态规划可处理负权重 |
负权重环（Negative Weight Cycle）：若存在负权重环，最短路径问题无意义（可无限转圈使路径权重无限减小）。
算法关系图
图遍历基础
├── BFS → Dijkstra（贪心） → A*（启发式）
├── BFS → Bellman-Ford（队列优化=SPFA）
└── 动态规划 → Floyd
相关概念
- 图：最短路径的载体
- BFS：无权图最短路径基础
- DFS：路径穷举基础
- 动态规划：Floyd 算法基础
- Dijkstra算法：单源最短路径经典算法