最短路径
01 / 共享的机制
从源点出发,到所有节点的最短距离。机制按边能携带什么分叉 —— 等权坍缩成 BFS,非负权要优先队列(Dijkstra),允许负权要做多轮松弛(Bellman-Ford), 全源距离则落到 Floyd-Warshall。
在上面选一个子模式。每个子模式都可以单独跳转 —— 从题目最像的那个开始。
↑ 选一个— / 什么时候用哪个
无权 BFS
当每条边的代价相同时使用 —— 一步 = 一条边。
网格 · 迷宫 · O(V + E)
Dijkstra
当边权非负时使用。
优先队列 · O((V + E) log V)
Bellman-Ford
当允许负权,或需要检测负环时使用。
V−1 轮松弛 · O(V · E)
Floyd-Warshall
当需要全源距离、而不仅是单源时使用。
经中转点 DP · O(V³)