今天介紹最後一種路徑演算法，也是最難的。

對於全源最短路徑問題，可以認為是單源最短路徑問題的推廣，即分別以每個頂點作為源頂點並求其至其它頂點的最短距離。例如，對每個頂點應用 Bellman-Ford 演算法，則可得到所有頂點間的最短路徑的運行時間為 O(V^2E)，由於圖中頂點都是連通的，而邊的數量可能會比頂點更多，這個時間沒有比 Floyd-Warshall 全源最短路徑演算法 O(V^3) 更優。那麼，再試下對每個頂點應用 Dijkstra 演算法，則可得到所有頂點間的最短路徑的運行時間為 O(VE + V^2logV)，看起來優於 Floyd-Warshall 演算法的 O(V^3)，所以看起來使用基於 Dijkstra 演算法的改進方案好像更好，但問題是 Dijkstra 演算法要求圖中所有邊的權值非負，不適合通用的情況。

在 1977 年，Donald B. Johnson 提出了對所有邊的權值進行 "re-weight" 的演算法，使得邊的權值非負，進而可以使用 Dijkstra 演算法進行最短路徑的計算。

我們先自己思考下如何進行 "re-weight" 操作，比如，簡單地對每條邊的權重加上一個數，使它們都變成正數，是否可行？

但顯然，原來a到d的最短距離是1+1+1=3，需要依次經過b,c兩點，大於直接連接兩點的路徑。如果簡單地全部加上1，還是通過b,c兩點，其距離變成2+2+2=6，而直接連接兩路的路徑變為5，直接導致最短路徑的變化，是不可行的。

那麼，Johnson 演算法是如何對邊的權值進行 **re-weight** 的呢？以下面的圖 G 為例，有 4 個頂點和 5 條邊。

首先，新增一個頂點 E，並使其與所有頂點連通，它到其他頂點的權重都為 0，即：

使用 Bellman-Ford 演算法 計算新的頂點到所有其它頂點(A, B,C, D)的最短路徑，得到[0,-5,-1,0], 存到一個變數h中 。然後移除E頂點，然後對所有邊的權重以下面的公式重新計算。

weight(start, end) = weight(start, end) + (h[start] - h[end])

於是有

ABw = -5 + h[0] - h[1] = -5 + 0 - (-5) = 0
BCw = 4 + h[1] - h[2] = 4 + -5 - (-1) = 0
CDw = 1 + h[2] - h[3] = 1 + -1 - 0 = 0
ADw = 3 + h[0] - h[3] = 3 + 0 - 0 = 3
ACw = 2 + h[0] - h[2] = 2 + 0 - (-1) = 3

現在所有邊為正數了，可以使用 Dijkstra演算法求解。

總結上面的過程，得到 Johnson 演算法的步驟如下：

1. 添加虛擬節點到這個圖裡，並添加指向所有節點的虛擬邊，這些邊的權重為 0

2. 以虛擬節點節點為起點，運行 Bellman-Ford演算法， 求出到每個節點的最短距離，存到h數組中

3. 移除虛擬節點，用上面求出的 h 值去更新圖裡的邊的權重，使得 `weight(start, end) = weight(start, end) + (h[start] - h[end])`

4. 對每個節點運行 Dijkstra 計算到其它節點的最短距離， 得到的distance數組的每個值需要減去 h[start] - h[end]

Bellman-Ford 演算法時間複雜度是 O(VE) ，Dijkstra 演算法的時間複雜度是O(Vlog(V)) ，因為每個節點都要做 Dijkstra，所以總的時間複雜度是O(V^2log(V)+VE) 。

其實現以下：

var COLOR = { //by司徒正美
 WHITE: void 666,
GRAY: 1,
BLACK: -1
}
class GraphByEdge {
constructor(vertices, isDirected = false) {//略
 }
insertEdge(from, to, weight) {//略
 }
addEdge(a, b, weight = 1) {
var from = this.map[a];
var to = this.map[b];
this.insertEdge(from, to, weight);
if (!this.isDirected) {
this.insertEdge(to, from, weight);
}
}
toString(obj){//略
 }
johnsons(){
var vertices = this.vertices;
var n = vertices.length;
//添加新點
 var virtual = "virtual"+n
this.map[virtual] = n;
this.vertices.push(virtual);
//保存舊邊
 var oldEdges = this.edges.concat();
//添加新邊
 for(var i = 0; i < n; i++){
this.addEdge(virtual, this.vertices[i], 0)
}
var { distance } = this.bellmanFord(virtual) ;
var h = distance
//還原
 delete this.map[virtual];
this.vertices.pop()
this.edges = oldEdges;
//re-weight
 this.edges.forEach(function(edge){
edge.weight = edge.weight+ (h[edge.from] - h[edge.to])
})
//對所有邊dijkstra
 var distSet = []
for (var i = 0; i < n; i++) {
distSet[i] = []
for (var j = 0; j < n; j++) {
distSet[i][j] = i == j ? 0 : Infinity
}
}
for (var begin = 0; begin < n; begin++) {
var obj = this.dijkstra(this.vertices[begin]);
var dist = obj.distance
for (var end = 0; end < dist.length; end++) {
if (dist[end] != Infinity) {
//減回之前加上的值
 distSet[begin][end] = dist[end] - (h[begin] - h[end]);
}
}
}
return distSet
}
bellmanFord(start) {
//略
 return {
hasCycle,
distance
}
}
dijkstra(start) {
//略
 return {
distance,
shortPaths
}
}
}

做幾個例子測試一下：

function logJohnsons(g) { //by司徒正美
 var distSet = g.johnsons()
console.log(g.toString(distSet))
}
//下面數據的來源見
 // https://www.jianshu.com/p/36bbe0e86765
 // https://www.cnblogs.com/gaochundong/p/johnson_algorithm.html
 // https://www.cnblogs.com/luweiseu/archive/2012/07/14/2591533.html
 var g = new GraphByEdge([A, B, C, D], true)
g.addEdge(A, B, -5);
g.addEdge(B, C, 4);
g.addEdge(C, D, 1);
g.addEdge(A, D, 3);
g.addEdge(A, C, 2);
logJohnsons(g)
console.log("========")

var g1 = new GraphByEdge([0, 1, 2, 3, 4], true)

g1.addEdge(0, 1, -1);
g1.addEdge(0, 2, 4);
g1.addEdge(1, 2, 3);
g1.addEdge(1, 3, 2);
g1.addEdge(1, 4, 2);
g1.addEdge(3, 2, 5);
g1.addEdge(3, 1, 1);
g1.addEdge(4, 3, -3);
logJohnsons(g1)
console.log("========")
var g2 = new GraphByEdge([0, 1, 2, 3], true);
g2.addEdge(0, 1, 5);
g2.addEdge(0, 3, 10);
g2.addEdge(1, 2, 3);
g2.addEdge(2, 3, 1);
logJohnsons(g2)


推薦閱讀：
相关文章