如何使用Python實作Floyd-Warshall演算法？

如何使用Python實作Floyd-Warshall演算法？

Floyd-Warshall演算法是一種用於解決所有源點到所有目標點的最短路徑問題的經典演算法。它是一種動態規劃演算法，可用於處理有向圖或負權邊問題。本文將介紹如何使用Python實作Floyd-Warshall演算法，以及提供具體的程式碼範例。

Floyd-Warshall演算法的核心思想是透過遍歷圖中的所有節點，以每個節點為中間節點，逐步更新節點間的最短路徑。我們可以使用一個二維矩陣來儲存圖中各節點之間的距離。

首先，我們需要定義一個函數來實作Floyd-Warshall演算法。以下是一個簡單的演算法框架：

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

這段程式碼使用了三個巢狀的迴圈來處理圖中的每個節點。在每一次迭代中，我們透過更新距離矩陣來找到更短的路徑。具體來說，我們將檢查從節點i到節點j的路徑是否可以透過節點k來實現更短的距離。如果是，我們就更新距離矩陣中的值。

在使用函數之前，我們需要定義一個圖。以下是一個範例圖的定義：

graph = [
    [0, float('inf'), -2, float('inf')],
    [4, 0, 3, float('inf')],
    [float('inf'), float('inf'), 0, 2],
    [float('inf'), -1, float('inf'), 0]
]

這個範例圖是一個有向圖的鄰接矩陣表示。其中，float('inf')表示距離為無窮大，這表示兩個節點之間沒有直接連接。

下面，我們呼叫floydWarshall函數，傳入圖表作為參數，並列印最終的結果：

result = floydWarshall(graph)
for row in result:
    print(row)

完整的程式碼如下：

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

graph = [
    [0, float('inf'), -2, float('inf')],
    [4, 0, 3, float('inf')],
    [float('inf'), float('inf'), 0, 2],
    [float('inf'), -1, float('inf'), 0]
]

result = floydWarshall(graph)
for row in result:
    print(row)

執行上述程式碼，你會得到以下輸出：

[0, -1, -2, 0]
[4, 0, 2, 4]
[5, 1, 0, 2]
[3, -1, 1, 0]

輸出的結果是一個二維矩陣，表示圖中任兩個節點之間的最短路徑。例如，result[0][2]的值為-2，表示從節點0到節點2的最短路徑距離為-2。如果兩個節點之間無法到達，則距離被標記為無限大。

透過這個實例，我們可以清楚地了解Floyd-Warshall演算法的實作和使用。希望本文能對你理解並運用該演算法有所幫助！

以上是如何使用Python實作Floyd-Warshall演算法？的詳細內容。更多資訊請關注PHP中文網其他相關文章！