floyd算法求最短路径怎么用

问题描述

精选答案

首先，在不考虑时间复杂度的情况下，同是解决图论中最短路径的寻找的问题。这个基础的问题之上还可以引申出很多其他的理论或是实际应用问题。

Dijkstra进行进一步的堆优化以后时间复杂度成为O(nlogn)，比起Floyd的O(n^3)是小了非常非常多。但是Dijkstra，以及常用的还有Bellman-Ford，SPFA等，均是在求

单源

最短路径的问题中有着较为理想的时间复杂度(<=O(n^2))，但若是求图中任意两点间的距离，尤其是在图较为稠密时，Floyd的O(n^3)也是不输于其他的。

另外Floyd有一个优势，那便是写起来简单。插点的简单思想，三重循环加一个判定，五行就写完了。而Dijkstra在堆优化后、以及SPFA，则需要约50行的代码。