关于floyd算法的疑问
  • 板块灌水区
  • 楼主Martlet
  • 当前回复8
  • 已保存回复8
  • 发布时间2023/1/13 08:15
  • 上次更新2023/10/24 04:30:14
查看原帖
关于floyd算法的疑问
543717
Martlet楼主2023/1/13 08:15

floyd算法的时间复杂度是O(N^3),dijkstra不优化的时间复杂度是O(N^2)。全局最短路相当于对n个点各做一次全局最短路,所以用dijkstra求全局最短路也是时间复杂度是O(N^3)。

但是,dijkstra堆优化的时间复杂度是O((m+n) * logn)

所以dijkstra求全局最短路也是时间复杂度是O((m+n)* logn *n)。

那为什么还用floyd求全局最短路?

2023/1/13 08:15
加载中...