最短路径四大算法

最短路径四大算法

最短路径四大算法：bellman-ford，dijkstra，spfa，floyd。

最短路径算法从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径叫做最短路径。解决最短路的问题有以下算法，Dijkstra算法，Bellman-Ford算法，Floyd算法和SPFA算法等。

扩展资料

bellman-ford可以用于边权为负的图中，图里有负环也可以，如果有负环，算法会检测出负环。

时间复杂度O（VE）;

dijkstra只能用于边权都为正的图中。

时间复杂度O（n2）；

spfa是个bellman-ford的优化算法，本质是bellman-ford，所以适用性和bellman-ford一样。（用队列和邻接表优化）。

时间复杂度O（KE）;

floyd可以用于有负权的图中，即使有负环，算法也可以检测出来,可以求任意点的最短路径，有向图和无向图的`最小环和最大环。

时间复杂度O（n3）；

任何题目中都要注意的有四点事项：图是有向图还是无向图、是否有负权边，是否有重边，顶点到自身的可达性。