johnson算法是什么？

Johson算法是目前最高效的在无负环可带负权重的网络中求所有点对最短路径的算法.

Johson算法是Bellman-Ford算法,

Reweighting(重赋权重)和Dijkstra算法的大综合.

对每个顶点运用Dijkstra算法的时间开销决定了Johnson算法的时间开销.

每次Dijkstra算法(d堆PFS实现)的时间开销是O(

E

*

lgd(V)

).

其中E为边数,

V为顶点数,

d为采用d路堆实现优先队列ADT.

所以,

此种情况下Johns...

Johnson算法适用于求All

Pairs

Shortest

Path.

Johnson算法应用了重标号技术，先进行一次Bellman-Ford算法，然后对原图进行重标号，w'(i,j)=h[i]-h[j]+w(i,j)。然后对每个点进行一次Dijkstra，每次Dijkstra的复杂度为O(nlogn+m)，于是算法复杂度为O(n^2logn+m)。

关于求解流水作业调度问题的

Johnson

算法具体描述:

标签：johnson,算法