Johnson算法的内容是怎么样的？

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 算法具体描述:
http://www.cnitblog.com/jsjzzm/archive/2006/11/07/18939.html