【johnson算法】johnson算法是什么?
答案:2 悬赏:30 手机版
解决时间 2021-02-26 09:03
- 提问者网友：姑娘长的好罪过
- 2021-02-25 23:33
【johnson算法】johnson算法是什么?
最佳答案
- 五星知识达人网友：慢性怪人
- 2021-02-26 00:29
【答案】 Johson算法是目前最高效的在无负环可带负权重的网络中求所有点对最短路径的算法. Johson算法是Bellman-Ford算法, Reweighting(重赋权重)和Dijkstra算法的大综合. 对每个顶点运用Dijkstra算法的时间开销决定了Johnson算法的时间开销. 每次Dijkstra算法(d堆PFS实现)的时间开销是O( E * lgd(V) ). 其中E为边数, V为顶点数, d为采用d路堆实现优先队列ADT. 所以, 此种情况下Johnson算法的时间复杂度是O( V * E * lgd(V) ).
全部回答
- 1楼网友：天凉才是好个秋
- 2021-02-26 01:25
这下我知道了
我要举报
如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
大家都在看
推荐资讯