心代码只有5行....
1 for (int k = 1; k <= n; k++)//枚举中间点
2 for (int i = 1; i <= n; i++)//枚举起点
3 for (int j = 1; j <= n; j++)//枚举终点
4 e[i][j] = min(e[i][j], e[i][k] + e[k][j]);//替换
大概就是说，从i点到j点是直接走比较近还是从i到k再从k到j这样绕一圈比较近，如果我绕一圈近的话就更新一下路径长度
完整代码
1 #include<iostream>
2 #include<vector>
3 #include<algorithm>
4 using namespace std;
5 int e[1000][1000];
6 int main()
7 {
8 int n, m;
9 cin >> n >> m;
10 for (int i = 1; i <= n; i++)
11 for (int j = 1; j <= m; j++)
12 if (i == j)
13 e[i][j] = 0;
14 else
15 e[i][j] = 9999999;
16 for (int i = 1; i <= m; i++)
17 {
18 int x, y, z;
19 cin >> x >> y >> z;
20 e[x][y] = z;
21 e[y][z] = z;
22 }
23 for (int k = 1; k <= n; k++)//枚举中间点
24 for (int i = 1; i <= n; i++)//枚举起点
25 for (int j = 1; j <= n; j++)//枚举终点
26 e[i][j] = min(e[i][j], e[i][k] + e[k][j]);//替换
27 return 0;
28 }
算法优点：
-
他求的是多源最短路，也就是说跑完一次Floyd，那么图中任意两个点之间的最短路就都知道了，不像后两种求的是单源最短路
-
好打
算法缺点：
2，Dijkstra
1 #include<iostream>
2 #include<algorithm>
3 using namespace std;
4 const long inf = 20041001;
5 int n;
6 int m;
7 int s;
8 int tot;
9 struct edge
10 {
11 long weight;
12 int to;
13 int next;
14 }e[500005];
15 struct node
16 {
17 int head;
18 }no[10086];
19 long long dis[10086];
20 bool book[10086];
21 void add(int from, int to, int weight)
22 {
23 tot++;
24 e[tot].to = to;
25 e[tot].weight = weight;
26 e[tot].next = no[from].head;
27 no[from].head = tot;
28 }
29 int main()
30 {
31 cin >> n >> m >> s;
32 book[s] = 1;
33 for (int i = 1; i <= n; i++)
34 dis[i] = inf;
35 dis[s] = 0;
36 for (int i = 1; i <= m; i++)
37 {
38 int x, y, w;
39 cin >> x >> y >> w;
40 if (x != y)
41 add(x, y, w);
42 }
43 for (int i = no[s].head; i; i = e[i].next)
44 {
45 if (e[i].weight < dis[e[i].to])
46 dis[e[i].to] = e[i].weight;
47 }
48 for (int i = 1; i < n; i++)
49 {
50 int u = 0;
51 int minn = inf;
52 for (int j = 1; j <= n; j++)
53 {
54 if (book[j] == 0 && dis[j] < minn)
55 {
56 minn = dis[j];
57 u = j;
58 }
59 }
60 book[u] = 1;
61 for (int i = no[u].head; i; i = e[i].next)
62 {
63 if (dis[e[i].to] > dis[u] + e[i].weight)
64 dis[e[i].to] = dis[u] + e[i].weight;
65 }
66 }
67 for (int i = 1; i <= n; i++)
68 cout << dis[i] << " ";
69 return 0;
70 }
算法优点
-
快了不少，好歹达到了O(n2)的复杂度，用堆儿优化之后甚至可以达到O((n+m)logn),算是比较优秀了
算法缺点
-
求的是单源最短路，也就是说我每次求完都只能知道点s到各个点的最短距离，如果我要求每个点的，也就要跑n次，就很慢了
3，Bellman Ford
1 #include<iostream>
2 #include<string.h>
3 #include<algorithm>
4 #include<vector>
5 #include<map>
6 #include<bitset>
7 #include<set>
8 #include<string>
9 #if !defined(_WIN32)
10 #include<bits/stdc++.h>
11 #endif // !defined(_WIN32)
12 #define ll long long
13 #define dd double
14 using namespace std;
15 int t;
16 int n, m, w;
17 int tot;
18 struct edge
19 {
20 int from;
21 int to;
22 int weight;
23 }e[100086];
24 int dis[5005];
25 void add(int x, int y, int z)
26 {
27 tot++;
28 e[tot].from = x;
29 e[tot].to = y;
30 e[tot].weight = z;
31 }
32 bool Bellman_Ford()
33 {
34 memset(dis, 0x3f3f3f3f, sizeof(dis));
35 dis[1] = 0;
36 for (int i = 1; i < n; i++)
37 {
38 for (int j = 1; j <= tot; j++)
39 {
40 if (dis[e[j].to] > dis[e[j].from] + e[j].weig