特别注释：n为代表顶点数量，m代表遍数

1.Floyd算法

时间复杂度

O(n^3)

空间复杂度

n^2

运用场景

快速查询平面坐标系上两点之间的(最短)距离

使用好处

简单易懂，使用便捷，三层for循环

使用限制

n<=400

2.BellmanFord/SPFA算法(bfs)

时间复杂度

O(nm)SPFA的最坏复杂度为O(nm)

空间复杂度

n*m

运用场景:

可处理负权边及负环检测，特别适用于有边数限制的最短路问题（如限制路径边数不超过 k 时）

使用好处

处理负边权搜索，可队列优化

使用限制:

但最坏情况下效率较低

3.Dijkstra算法(邻接表或邻接矩阵)

时间复杂度

n^2(邻接矩阵)/n+m(邻接表)

空间复杂度

n*m

运用场景

单源最短路径

使用好处

可用(大小)堆优化，提高运行效率

使用限制

不可用含负数边权的搜索和多次异点查询

4详细可见：

具体课件(校外)

具体课件(校内)

推荐题目

1.B3647. 【模板】Floyd

2.【模板】传递闭包

3.【模板】负环

4.【模板】单源最短路径（标准版）

5.【例4-1】最短路径问题【Floyd模板】

6.最短路计数