a*算法求最短路径和floyd还有dijsktra算法求最短路径的区别?

a*算法求最短路径和floyd还有dijsktra算法求最短路径的区别?
a*算法求最短路径和floyd还有dijsktra算法求最短路径的区别?

a*算法求最短路径和floyd还有dijsktra算法求最短路径的区别?
A*算法是启发式搜索,适合点对点的最短路径,单源单汇的情况
Floyd是动态规划的一种,可以求出任意两点之间的最短路径
Dijkstra是贪婪算法的一种,求一点到其他所有点的最短路,即所谓的单源最短路算法
从时间复杂度来说
Floyd是O(N^3)
Dijkstra是O(N^2)
而启发式搜索就不好说了……
结果当然是一样的,都是最短路,但是适用情形和时空开销就不同了
举例来说,你做任意两点间最短路可以用N次Dijkstra或者1次Floyd,时间消耗一样,显然用后者,而如果你只用求两点间的,用Floyd就不合算了