Floyd-Warshall algorthm如何工作，什麼是K？

我很難理解Floyd-Warshall algorithm。我知道它是如何工作的因爲我知道如何手工完成，但我需要通過計算機瞭解它洞察力。Floyd-Warshall algorthm如何工作，什麼是K？

FOR k <-- 1 TO N DO 
    FOR i <-- 1 TO N DO 
     FOR j <-- TO N DO 
      IF Djk + Dkj < DiJ THEN 
       Dij <-- djk + dkj

k，i和j是迭代變量，它遍歷直到n價值，我想這是一個嵌套循環，然後它看起來在每個節點不到它找到最短路徑？

2011-11-23 Benjamin

查找「三角形不等式」 – wildplasser

或去訪問http://cstheory.stackexchange.com – sehe

cstheory是研究級別CS所以問題屬於這裏。也就是說OP需要處理這些0 upvotes和0接受的答案 – hugomg

Floyd-Warshall中k的簡化含義是圖中的「方式點」。最後兩行可以解釋如下：「如果通過迄今爲止發現的任何路徑，從i到k然後從k到j快於從i到j，那麼從i到j到k的路徑變成新的最短路徑「。

2011-11-23 18:39:49 dasblinkenlight

K表示中間頂點。所以，外層循環基本上說讓第K個頂點成爲中間停留點。然後內部兩個循環檢查鄰接矩陣中的每個項目，並檢查使用K（使用K作爲中間頂點）的距離是否小於從頂點i到j的距離（鄰接位置i，j中的數字矩陣）。如果距離較小，則更新d [i，j]。

2014-06-01 22:08:18

回答