最短路径四大算法
回答
爱扬教育
2022-08-15
- 相关推荐
最短路径算法从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径叫做最短路径。解决最短路的问题有以下算法，Dijkstra算法，Bellman-Ford算法，Floyd算法和SPFA算法等。
扩展资料
bellman-ford可以用于边权为负的图中，图里有负环也可以，如果有负环，算法会检测出负环。
时间复杂度O（VE）;
dijkstra只能用于边权都为正的图中。
时间复杂度O（n2）；
spfa是个bellman-ford的优化算法，本质是bellman-ford，所以适用性和bellman-ford一样。（用队列和邻接表优化）。
时间复杂度O（KE）;
floyd可以用于有负权的图中，即使有负环，算法也可以检测出来,可以求任意点的最短路径，有向图和无向图的最小环和最大环。
时间复杂度O（n3）；
任何题目中都要注意的有四点事项：图是有向图还是无向图、是否有负权边，是否有重边，顶点到自身的可达性。