floyd-warshall演算法詳解

一、floyd-warshall演算法

floyd-warshall演算法是一種用於解決所有節點對之間的最短路徑問題的演算法。該演算法基於動態規劃的思想，它採用的是一種分治的策略，在不斷迭代中使得問題規模逐漸減小。該演算法的時間複雜度為O(n^3)。

floyd-warshall演算法是以「中間節點」為分界線，通過將中間節點逐漸加入，從而得到所有節點對之間的最短路徑。具體實現時，需要在二維矩陣中設置三維數組，第三維表示中間節點，依次遍歷每個中間節點，然後計算出以該節點為中間節點的最短距離。

二、floyd-warshall演算法空間複雜度

考慮到實際應用中圖的節點數很大，如果使用鄰接矩陣進行全對全最短路徑計算，空間開銷將會非常大。具體而言，對於一個大小為n的圖，鄰接矩陣佔用的空間複雜度為O(n^2)。由此， floyd-warshall演算法的空間複雜度也將達到O(n^3)。但是，可以通過優化空間的方法進行改善，具體而言，可以設置一個n*n的矩陣，其中的每個元素表示從i節點到j節點的最短路徑，每次迭代只需要更新矩陣的一部分，這樣可以將空間複雜度降低到O(n^2)。

三、floyd-warshall怎麼讀

floyd-warshall演算法是由兩位科學家Robert Floyd 和 Stephen Warshall 合作提出的演算法，因此，讀作「floyd-沃舍爾演算法」。

四、floyd-warshall演算法圖解

下圖是一個採用floyd-warshall演算法求取兩個節點之間最短路徑的示意圖。其中，紅色數字表示每個節點的編號，黑色數字表示兩個節點之間的距離。

<img src="fw.png" alt="floyd-warshall演算法圖解">

在該圖中，我們可以看到，如果要求節點1到8之間的最短路徑，那麼我們可以通過不斷迭代，分別將2、3、5、6、7加入，最終得到節點1到8之間的最短距離為14。

五、floyd-warshall三重循環

下面是floyd-warshall演算法的主要實現函數：

def floydWarshall(graph):    
    dist = list(map(lambda i : list(map(lambda j : j , i)) , graph))    
    for k in range(len(graph)):         
        for i in range(len(graph)):             
            for j in range(len(graph)):                 
                dist[i][j] = min(dist[i][j] , dist[i][k]+ dist[k][j])    
    return dist

該函數使用了三重循環，其中第一重循環遍歷中間節點，第二重循環遍歷起始節點，第三重循環遍歷結束節點，具體實現時，每次迭代更新dist[i][j]的值，使之成為經過中間節點k的最短路徑。

六、floyd-warshall演算法中的k

floyd-warshall演算法中的k表示中間節點，當我們遍歷每個k時，相當於將其當作中轉站，來計算兩個節點之間的距離。在具體實現時，我們可以使用三重循環來遍歷每個節點對之間的距離，並不斷更新dist[i][j]的值。

七、floyd-warshall演算法時間複雜度

floyd-warshall演算法的時間複雜度為O(n^3)。這是因為，在計算最短路徑時，需要遍歷所有的中間節點，而對於每個中間節點，都需要遍歷一遍所有的節點對，因此總的遍歷次數為n*n*n。

八、floyd-warshall演算法思想

floyd-warshall演算法的思想是「分治」，即將每個中間節點當作中轉站，來計算兩個節點之間的距離。具體而言，我們可以使用一個二維矩陣來存儲每兩個節點之間的距離，然後通過逐步加入中間節點，來求取所有節點對之間的距離。

九、floyd-warshall演算法貪心

floyd-warshall演算法並不是一種貪心演算法。它是一種基於動態規劃的演算法，它採用的是一種分治的策略，在不斷迭代中使得問題規模逐漸減小。

十、floyd-warshall演算法求負環

floyd-warshall演算法也可以用來判斷圖中是否存在負環。具體而言，在floyd-warshall演算法求得所有節點之間最短路徑的過程中，如果某一次迭代中dist[i][i]出現了負數，那麼就說明圖中存在負環。

下面是代碼示例：

def floydWarshall(graph):    
    dist = list(map(lambda i : list(map(lambda j : j , i)) , graph))    
    for k in range(len(graph)):         
        for i in range(len(graph)):             
            for j in range(len(graph)):                 
                dist[i][j] = min(dist[i][j] , dist[i][k]+ dist[k][j])    
        if dist[k][k] < 0:            
            return "存在負環"    
    return dist

上述代碼中，如果在某一次迭代中dist[k][k]出現了負數，那麼該函數就會返回「存在負環」。