图中的路径问题，特别是最短路径问题是图论中算法的核心，今天 就来总结 一下。
BFS求无权最短径
对于 无权图，用BFS就能找到两个节点之间的最短路径，这是BFS的天然优势。遍历 的时候 要注意 用「圈层式」遍历，也就是说对于 当前节点，把其相邻节点遍历 完，才能算走了一步。
Dijkstra求有向无环带权图的最短路径
对于有向无环图DAG，带有权重的最短路径问题可以用Dijkstra算法来求解。具体参见Understanding Dijkstra Algorithm。
Floyd
Bellman Ford
Bellman Ford算法能处理负权重，这是与其他算法不同之处。
SPFA
Shortest Path Faster Algorithm，SPFA，基于Bellman Ford优化出来的更快速的算法。SPFA is an optimization of Bellman Ford algorithm.
- Bellman-Ford Algorithm
- Shortest Paths Faster - SPFA Algorithm?
- Shortest Path Faster Algorithm (SPFA)
典型问题
| 题目 | 题解 | 说明 |
|---|---|---|
| 787. K 站中转内最便宜的航班 | 题解 | |
| 1928. 规定时间内到达终点的最小花费 | 题解 | 787的变种 |
| 题解 | ||
| 题解 |