c++_csp-j算法 (3)

弗洛伊德算法（Floyd）

Floyd算法又稱為插點法，是一種利用動態規劃的思想尋找給定的加權圖中多源點之間最短路徑的算法，與Dijkstra算法類似。該算法名稱以創始人之一、1978年圖靈獎獲得者、斯坦福大學計算機科學系教授羅伯特·弗洛伊德命名。

介紹

弗洛伊德算法（Floyd算法）是一種用于解決圖中任意兩點之間的最短路徑的算法。它是一種動態規劃算法，由羅伯特·弗洛伊德（Robert Floyd）于1962年提出。弗洛伊德算法的基本思想是通過中間節點的遞歸遍歷，逐步更新圖中任意兩點之間的最短路徑。弗洛伊德算法的時間復雜度為O(n^3)，適用于解決稠密圖中任意兩點之間的最短路徑問題。

弗洛伊德算法的應用領域非常廣泛，包括網絡路由算法、圖像處理、自動化規劃等。在網絡路由算法中，弗洛伊德算法常用于計算路由表，以確定網絡中任意兩點之間的最短路徑。在圖像處理中，弗洛伊德算法常用于圖像分割、圖像匹配等領域。在自動化規劃中，弗洛伊德算法常用于路徑規劃、機器人導航等應用。

弗洛伊德算法的核心思想是動態規劃。在計算任意兩點之間的最短路徑時，弗洛伊德算法通過遞歸遍歷中間節點，逐步更新最短路徑。具體步驟如下：

初始化：將圖中任意兩點之間的距離初始化為無窮大，將圖中任意兩點之間的直接距離初始化為它們之間的距離。將中間節點初始化為無窮大。
遞歸更新：遍歷圖中的所有節點，以每個節點為中間節點，更新任意兩點之間的最短路徑。具體步驟如下：
- 對于每一對節點i、j，以節點k為中間節點，更新節點i、j之間的距離：如果節點i、j之間的距離大于節點i、k之間的距離加上節點k、j之間的距離，則更新節點i、j之間的距離為節點i、k之間的距離加上節點k、j之間的距離。
重復遞歸：重復步驟2，直到所有節點為中間節點的最短路徑都被更新。
輸出最短路徑：最終得到任意兩點之間的最短路徑。

弗洛伊德算法的時間復雜度為O(n^3)，空間復雜度為O(n^2)，其中n為圖中節點的個數。弗洛伊德算法的優點是能夠解決任意兩點之間的最短路徑問題，適用于解決稠密圖中的最短路徑問題。弗洛伊德算法的缺點是時間復雜度較高，對于大規模圖的計算較為耗時。

總之，弗洛伊德算法是一種用于解決圖中任意兩點之間的最短路徑的動態規劃算法。它的核心思想是通過遞歸遍歷中間節點，逐步更新最短路徑。弗洛伊德算法在網絡路由算法、圖像處理、自動化規劃等領域有廣泛的應用。弗洛伊德算法的時間復雜度為O(n^3)，適用于解決稠密圖中的最短路徑問題。弗洛伊德算法是圖算法中的重要算法之一，對于解決圖中的最短路徑問題具有重要的意義。

### 1. 弗洛伊德算法的基本思想

弗洛伊德算法的基本思想是動態規劃。在計算任意兩點之間的最短路徑時，算法通過遞歸遍歷中間節點，逐步更新最短路徑。算法的核心在于利用中間節點的遞歸思想，通過動態規劃的方式逐步優化路徑長度，最終得到圖中所有節點之間的最短路徑。

### 2. 弗洛伊德算法的核心步驟

弗洛伊德算法的核心步驟包括初始化和遞歸更新兩個階段：

#### 2.1 初始化階段

1. 將圖中任意兩點之間的距離初始化為無窮大，將圖中任意兩點之間的直接距離初始化為它們之間的距離。
2. 將中間節點的距離初始化為無窮大。

#### 2.2 遞歸更新階段

1. 遍歷圖中的所有節點，以每個節點為中間節點，更新任意兩點之間的最短路徑。
2. 對于每一對節點i、j，以節點k為中間節點，更新節點i、j之間的距離：如果節點i、j之間的距離大于節點i、k之間的距離加上節點k、j之間的距離，則更新節點i、j之間的距離為節點i、k之間的距離加上節點k、j之間的距離。

#### 2.3 重復遞歸階段

重復遞歸更新階段，直到所有節點為中間節點的最短路徑都被更新。

#### 2.4 輸出最短路徑

最終得到圖中所有節點之間的最短路徑。

### 3. 弗洛伊德算法的時間復雜度

弗洛伊德算法的時間復雜度為O(n^3)，其中n為圖中節點的個數。算法中的三重循環是導致時間復雜度較高的原因，因此在大規模圖的計算中，算法可能會耗費較長時間。

### 4. 弗洛伊德算法的優點和缺點

#### 4.1 優點：

- 能夠解決任意兩點之間的最短路徑問題，適用于解決稠密圖中的最短路徑問題。
- 算法思想簡單，易于理解和實現。

#### 4.2 缺點：

- 時間復雜度較高，對于大規模圖的計算可能會耗費較長時間。
- 空間復雜度較高，需要維護大量的中間節點距離信息。

### 5. 弗洛伊德算法的應用

弗洛伊德算法在網絡路由算法、圖像處理、自動化規劃等領域有廣泛的應用。在網絡路由算法中，弗洛伊德算法常用于計算路由表，以確定網絡中任意兩點之間的最短路徑。在圖像處理中，弗洛伊德算法常用于圖像分割、圖像匹配等領域。在自動化規劃中，弗洛伊德算法常用于路徑規劃、機器人導航等應用。

### 6. 總結

弗洛伊德算法是一種經典的動態規劃算法，用于解決圖中任意兩點之間的最短路徑問題。算法通過遞歸遍歷中間節點，逐步更新最短路徑，最終得到圖中所有節點之間的最短路徑。弗洛伊德算法的時間復雜度為O(n^3)，適用于解決稠密圖中的最短路徑問題。算法在網絡路由算法、圖像處理、自動化規劃等領域有廣泛的應用，是圖算法中的重要算法之一。弗洛伊德算法的優點是能夠解決任意兩點之間的最短路徑問題，易于理解和實現，但缺點是時間復雜度較高，對于大規模圖的計算可能會耗費較長時間。

算法實現

弗洛伊德算法（Floyd算法）是一種經典的動態規劃算法，用于解決圖中任意兩點之間的最短路徑問題。該算法的實現涉及到圖的表示、距離矩陣的初始化、動態規劃的遞歸更新等步驟。在本節中，我們將詳細介紹弗洛伊德算法的實現過程，包括算法的偽代碼、代碼實現、時間復雜度分析等內容。

### 1. 弗洛伊德算法的偽代碼

下面是弗洛伊德算法的偽代碼實現：

```
procedure FloydWarshall (graph)
? ? let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
? ? let next be a |V| × |V| array of vertex indices initialized to NULL

? ? for each edge (u, v) in graph
? ? ? ? dist[u][v] = graph[u][v]
? ? ? ? next[u][v] = v

? ? for each vertex v in graph
? ? ? ? dist[v][v] = 0
? ? ? ? next[v][v] = v

? ? for k from 1 to |V|
? ? ? ? for i from 1 to |V|
? ? ? ? ? ? for j from 1 to |V|
? ? ? ? ? ? ? ? if dist[i][j] > dist[i][k] + dist[k][j]
? ? ? ? ? ? ? ? ? ? dist[i][j] = dist[i][k] + dist[k][j]
? ? ? ? ? ? ? ? ? ? next[i][j] = next[i][k]
```

### 2. 弗洛伊德算法的代碼實現（Python示例）

下面是弗洛伊德算法的Python代碼實現示例：

```python
def floyd_warshall(graph):
? ? dist = [[float('inf') for _ in range(len(graph))] for _ in range(len(graph))]
? ? next = [[None for _ in range(len(graph))] for _ in range(len(graph))]

? ? for u in range(len(graph)):
? ? ? ? for v in range(len(graph)):
? ? ? ? ? ? dist[u][v] = graph[u][v]
? ? ? ? ? ? next[u][v] = v

? ? for v in range(len(graph)):
? ? ? ? dist[v][v] = 0
? ? ? ? next[v][v] = v

? ? for k in range(len(graph)):
? ? ? ? for i in range(len(graph)):
? ? ? ? ? ? for j in range(len(graph)):
? ? ? ? ? ? ? ? if dist[i][j] > dist[i][k] + dist[k][j]:
? ? ? ? ? ? ? ? ? ? dist[i][j] = dist[i][k] + dist[k][j]
? ? ? ? ? ? ? ? ? ? next[i][j] = next[i][k]

? ? return dist, next
```

### 3. 弗洛伊德算法的時間復雜度分析

弗洛伊德算法的時間復雜度為O(n^3)，其中n為圖中節點的個數。算法中的三重循環是導致時間復雜度較高的原因。在實際應用中，算法的時間復雜度可能在處理大規模圖的情況下導致較長的計算時間。

### 4. 弗洛伊德算法的應用示例

下面是一個簡單的示例，展示如何使用弗洛伊德算法計算圖中任意兩點之間的最短路徑：

```python
graph = [
? ? [0, 3, 8, float('inf')],
? ? [float('inf'), 0, 2, 4],
? ? [float('inf'), float('inf'), 0, 1],
? ? [float('inf'), float('inf'), float('inf'), 0]
]

distances, next_vertices = floyd_warshall(graph)

print("Shortest distances between each pair of vertices:")
for i in range(len(graph)):
? ? for j in range(len(graph)):
? ? ? ? if distances[i][j] == float('inf'):
? ? ? ? ? ? print(f"Distance from vertex {i} to vertex {j} is infinity")
? ? ? ? else:
? ? ? ? ? ? print(f"Distance from vertex {i} to vertex {j} is {distances[i][j]}")
```

### 5. 總結

弗洛伊德算法是一種經典的動態規劃算法，用于解決圖中任意兩點之間的最短路徑問題。算法的實現涉及到圖的表示、距離矩陣的初始化、動態規劃的遞歸更新等步驟。通過遞歸更新中間節點，算法能夠高效地計算圖中任意兩點之間的最短路徑。弗洛伊德算法在網絡路由算法、圖像處理、自動化規劃等領域有廣泛的應用，是圖算法中的重要算法之一。

整體代碼

#include <iostream>
#include <vector>
#include <climits>using namespace std;const int INF = 1e9; // 定義無窮大int main() {int n, m;cin >> n >> m;// 初始化距離矩陣vector<vector<int>> dist(n + 1, vector<int>(n + 1, INF));// 自身到自身的距離為0for (int i = 1; i <= n; ++i) {dist[i][i] = 0;}// 讀取邊并處理重邊for (int i = 0; i < m; ++i) {int u, v, w;cin >> u >> v >> w;if (w < dist[u][v]) {dist[u][v] = w;dist[v][u] = w;}}// Floyd-Warshall算法for (int k = 1; k <= n; ++k) {for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n; ++j) {if (dist[i][k] != INF && dist[k][j] != INF) {dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);}}}}// 輸出結果for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n; ++j) {if (dist[i][j] == INF) {cout << "0 "; // 根據題目描述，邊權都是正整數，所以不可達的情況可能不存在，但按題意輸出0} else {cout << dist[i][j] << " ";}}cout << endl;}return 0;
}