將Floyd-Warshall限制爲路徑長度k

Question

我正在實施Floyd-Warshall algorithm。

我有大約50個節點的全圖，我想找到所有節點之間的最大路徑。 該算法返回的路徑可以是任意長度1 < x < 50，我需要這個長度最多是3-4個邊長，我怎樣才能改變算法呢？

Answer 1

讓w(i,j)是體重從我到Ĵ。然後可以計算

def shortest(w1, w2): 
    w12 = a new V x V matrix 
    for i in V: 
    for j in V: 
     w12(i, j) = w1(i, j) 
     for k in V: 
     if w12(i, j) > w1(i, k) + w2(k, j): 
      w12(i, j) = w1(i, k) + w2(k, j) 
    return w12 

w2 = shortest(w, w) 
w3 = shortest(w2, w) 
w4 = shortest(w2, w2) 

在結束時，w4將包含對於每一對，從開始的距離使用多達4個邊緣結束，並且類似地爲w3。請注意，您可以首先計算w4而不計算w3。使用這種形式的二值化，即計算和組合所有冪數矩陣，可以實現O（n 3 log k）的時間複雜度，即在最大路徑長度上只有對數。

維基百科上面有一篇關於算法的簡短文章。它的標題是「min-plus matrix multiplication」。也許一些與這個術語相關的參考文獻，或者替代術語「距離產品」，將導致關於可能實現的進一步信息。例如，有一篇文章「faster funny matrix multiplication for the all-pairs shortest paths problem」討論了這個問題，給出了一些算法，並考慮了SIMD的實現。