梦中旧人 3星
共回答了35个问题采纳率:96.2% 评论
首先,在不考虑时间复杂度的情况下,同是解决图论中最短路径的寻找的问题。这个基础的问题之上还可以引申出很多其他的理论或是实际应用问题。
Dijkstra进行进一步的堆优化以后时间复杂度成为O(nlogn),比起Floyd的O(n^3)是小了非常非常多。但是Dijkstra,以及常用的还有Bellman-Ford,SPFA等,均是在求
单源
最短路径的问题中有着较为理想的时间复杂度(<=O(n^2)),但若是求图中任意两点间的距离,尤其是在图较为稠密时,Floyd的O(n^3)也是不输于其他的。另外Floyd有一个优势,那便是写起来简单。插点的简单思想,三重循环加一个判定,五行就写完了。而Dijkstra在堆优化后、以及SPFA,则需要约50行的代码。
13小时前
猜你喜欢的问题
2天前1个回答
2天前1个回答
2天前1个回答
2天前2个回答
2天前1个回答
2天前2个回答
热门问题推荐
3个月前1个回答
1个月前2个回答
3个月前1个回答
2个月前1个回答
1个月前3个回答
3个月前1个回答
1个月前1个回答
3个月前1个回答
2个月前2个回答