Floyd算法(求解多源最短路问题)

Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。

在算法竞赛中求解最短路问题常见的一般就是这几种算法，dijkstra，spfa，bellman-ford和Floyd，前三个都是属于求单源最短路问题的算法，而后者是属于求解多源最短路问题的，可见，在求多源最短路过程中，能选择的算法寥寥可数。

Floyd算法和核心就是利用了动态规划的思想，把两个点之间的距离不断通过利用中间的其他节点来优化，从而达到最优距离。

Floyd模板：

 1 #include
 2 #include
 3 #include
 4 #include
 5 #include
 6 #include
 7 #include<set>
 8 #include
 9 #include
10 #include
11 #include<string>
12 #define ll long long
13 #define ull unsigned long long
14 #define inf 0x3f3f3f3f
15 #define inff 0x7fffffff
16 using namespace std;
17 const int N = 200 + 10;
18 const int M = 1000000 + 10;
19 const ll mod = 1e9 + 7;
20 
21 int G[N][N];
22 int n, m, k;
23 
24 void init() {
25     for (int i = 1; i <= n; i++) {
26         for (int j = 1; j <= n; j++) {
27             if (i == j) G[i][j] = 0;
28             else G[i][j] = inf;
29         }
30     }
31 }
32 
33 void floyd() {
34 
35     for (int k = 1; k <= n; k++) {
36         for (int i = 1; i <= n; i++) {
37             for (int j = 1; j <= n; j++) {
38                 if (G[i][k] + G[k][j] < G[i][j]) {
39                     G[i][j] = G[i][k] + G[k][j];
40                 }
41             }
42         }
43     }
44 
45     return;
46 }
47 
48 int main() {
49 
50     //int n, m, k;
51     cin >> n >> m >> k;
52     init();
53     for (int i = 1; i <= m; i++) {
54         int u, v, w;
55         cin >> u >> v >> w;
56         G[u][v] = min(G[u][v], w);
57     }
58     floyd();
59     while (k--) {
60         int u, v;
61         cin >> u >> v;
62         if (G[u][v] > inf / 2) cout << "impossible" << "\n";
63         else cout << G[u][v] << "\n";
64     }
65 
66     return 0;
67 }
   
最短路问题

相关

最短路问题——弗洛伊德算法(Floyd)

最短路问题

标签