最短路径-Floyd_warshall算法

Floyd算法,也称为Floyd-Warshall算法,是一种用于解决多源最短路径问题的算法。它可以用于计算任意两点之间的最短路径,并可以用于解决其他相关问题,例如最短路径树和最长路径。

Floyd算法的工作原理是通过动态规划来计算所有点对之间的最短路径。它首先初始化一个距离矩阵,其中每个元素表示两个点之间的初始距离。然后,算法迭代地更新距离矩阵,每次更新都会考虑通过中间节点的路径。

Floyd算法的具体步骤如下:

  1. 初始化距离矩阵 D,其中 D[i, j] 表示从点 i 到点 j 的初始距离。如果 i 和 j 之间存在直接连接,则 D[i, j] 等于直接连接的距离;否则,D[i, j] 等于无穷大。
  2. 对于所有中间节点 k,执行以下步骤:
    • 对于所有点 i 和 j,更新 D[i, j]:
      • 如果 D[i, j] > D[i, k] + D[k, j],则将 D[i, j] 更新为 D[i, k] + D[k, j]。
  3. 算法结束后,距离矩阵 D 中的每个元素将表示两个点之间的最短路径。


代码实现:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/**************************************************************** 
 * Description: 给定图G,求任意两点的最短路径,Floyd_warshall算法
 * Author: Alex Li
 * Date: 2024-02-23 12:27:10
 * LastEditTime: 2024-02-23 12:45:00
****************************************************************/
#include <iostream>
#include <vector>

using namespace std;

int main() {
  // 图的节点数
  int n;
  cin>>n;

  // 距离矩阵
  vector<vector<int> > distance_matrix(n, vector<int>(n));

  // 初始化距离矩阵
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (i == j) {
        distance_matrix[i][j] = 0;
      } else {
        distance_matrix[i][j] = INT_MAX;
      }
    }
  }

  // 输入图的边
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      int u, v, w;
      cin >> u >> v >> w;
      distance_matrix[u][v] = w;
    }
  }

  // Floyd 算法
  for (int k = 0; k < n; k++) {
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        if (distance_matrix[i][j] > distance_matrix[i][k] + distance_matrix[k][j]) {
          distance_matrix[i][j] = distance_matrix[i][k] + distance_matrix[k][j];
        }
      }
    }
  }

  // 输出距离矩阵
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cout << distance_matrix[i][j] << " ";
    }
    cout << endl;
  }

  return 0;
}
Scroll to Top