POJ-2387.Til the Cows Come Home.(五种方法：Dijkstra + Dijkstra堆优化 + Bellman-Ford + SPFA + Floyd-Warshall)

　　昨天刚学习完最短路的算法，今天开始练题发现我是真的菜呀，居然能忘记邻接表是怎么写的，真的是菜的真实......

为了弥补自己的菜，我决定这道题我就要用五种办法写出，并在Dijkstra算法堆优化中另外给出邻接表存储实现的操作，唉，真是令人窒息......

　　言归正传吧，毕竟我这么菜，也不会讲什么大道理......

　　呜哇呜哇.jpg

　　原题链接

　　本题大意：给定n结点，a和b表示其中的两个结点，输出t组a和b和w表示a和b距离w可以互相抵达，求从n走到1的最短路径...

　　本题思路：建图之后直接单源最短路任意结点之间的最短路随便解，只是有些算法会超时，我这里仅是作为练习算法去练习其他算法，读者可自行尝试......

　　先给出解决无负权单源最短路的最优算法Dijkstra算法吧，包括其优化：　　

　　　　Dijkstra ：我再叙述一下这个算法的作用机理吧，将整个图的结点分为两个部分，一部分为已经确定最短路径的集合S，另一部分当然是n - S，初始状态下S内不包含任何结点。接着在n - S中挑选一个权值最小的结点，将该结点直接

　　放进S中表示改结点到源结点的最短路径求解完毕，在n - S中对所有与该结点有公共边的结点做松弛操作，松弛的大体意思就是通过已知的最短路来求解与他相连的边的结点的最短路......

　　　　为啥上面我们要在n - S中寻找结点做松弛操作呢，因为S中的结点已经被求出了最短路，那为什么每次找的那个最小值就保证它已经是最短路了呢?这......证明简直花了算法导论一大堆篇章，我看懂了但我不说emm...(其实还是不懂...

　　小声bb.jpg)

　　参考代码：

　　　　好了，我们要开始写代码了

　　　　首先给出没有用堆优化的Dijkstra算法：

 1 //Dijkstra未优化版 ： 47ms
 2 #include <iostream>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 const int maxn = 1e3 + 5, INF = 0x3f3f3f3f;
 7 int t, n, k, dist[maxn], G[maxn][maxn];
 8 bool vis[maxn];
 9 
10 int Dijkstra(int source) {
11     for(int i = 1; i <= n; i ++)
12         dist[i] = (i == source ? 0 : INF);
13     for(int i = 1; i <= n; i ++) {
14         int Min = INF;
15         for(int j = 1; j <= n; j ++)
16             if(!vis[j] && dist[j] < Min) {
17                 Min = dist[j];
18                 k = j;
19             }
20         vis[k] = true;
21         for(int j = 1; j <= n; j ++) {
22             if(G[k][j] != INF && !vis[j] && dist[j] > dist[k] + G[k][j])
23                 dist[j] = dist[k] + G[k][j];
24         }
25     }
26     return dist[n];
27 }
28 
29 int main () {
30     cin >> t >> n;
31     int a, b, w;
32     memset(vis, false, sizeof vis);
33     for(int i = 1; i <= n; i ++)
34         for(int j = 1; j <= n; j ++)    
35             G[i][j] = INF;
36     for(int i = 0; i < t; i ++) {
37         cin >> a >> b >> w;
38         G[a][b] = min(G[a][b], w);
39         G[b][a] = min(G[b][a], w);
40     }
41     cout << Dijkstra(1) << endl;
42     return 0;
43 }

View Code

　　　　唉，烦人的Vj，每次给的Test time都不一样......

　　　　邻接矩阵存储的堆优化的Dijkstra算法：

 1 //堆优化的Dijkstra算法: 141ms
 2 #include <iostream>
 3 #include <cstring>
 4 #include <queue>
 5 #include <vector>
 6 using namespace std;
 7 
 8 typedef pair<int, int> Pii;
 9 const int maxn = 1000 + 5, INF = 0x3f3f3f3f;
10 int t, n, dist[maxn];
11 bool vis[maxn];
12 struct edge {
13     int to, cost;
14 };
15 vector <edge> G[maxn];
16 
17 void addedge(int u, int v, int w) {
18     G[u].push_back({v, w});
19 }
20 
21 int Dijkstra(int source) {
22     for(int i = 1; i <= n; i ++)    
23         dist[i] = (i == source ? 0 : INF);
24     priority_queue <Pii, vector<Pii>, greater<Pii> > Q;
25     Q.push(make_pair(0, 1));
26     while(!Q.empty()) {
27         Pii p = Q.top();
28         Q.pop();
29         if(vis[p.second]) continue;
30         vis[p.second] = true;
31         for(int i = 0; i < G[p.second].size(); i ++) {
32             edge e = G[p.second][i];
33             if(dist[e.to] > dist[p.second] + e.cost) {
34                 dist[e.to] = dist[p.second] + e.cost;
35                 Q.push(make_pair(dist[e.to], e.to));
36             }
37         }
38     }
39     return dist[n];
40 }
41 
42 int main () {
43     cin >> t >> n;
44     int a, b, w;
45     for(int i = 0; i < t; i ++) {
46         cin >> a >> b >> w;
47         addedge(a, b, w);
48         addedge(b, a, w);
49     }
50     cout << Dijkstra(1) << endl;
51     return 0;
52 }

View Code

　　　　Bellman-Ford：下面叙述一下Bellman-Ford算法的作用机理。

　　(1)初始化：将除源点外的所有顶点的最短距离估计值 d[v] ←+∞, d[s] ←0;

　　(2)迭代求解：反复对边集E中的每条边进行松弛操作，使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离；（运行|v|-1次）

　　(3)检验负权回路：判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点，则算法返回false，表明问题无解；否则算法返回true，并且从源点可达的顶点v的最短距离保存在 d[v]中。

　　下面我们给出该算法的代码：

 1 // /*Bellman-Ford算法：172ms
 2 #include <iostream>
 3 #include <cstring>
 4 #include <vector>
 5 using namespace std;
 6 
 7 typedef pair<int, int> Pii;
 8 struct edge {
 9     int to, cost;
10 };
11 const int maxn = 1000 + 5, INF = 0x3f3f3f3f;
12 vector <edge> G[maxn];
13 int t, n, dist[maxn];
14 
15 void addedge(int u, int v, int w) {
16     G[u].push_back({v, w});
17 }
18 
19 int Bellman_Ford(int source) {
20     bool flag;
21     for(int i = 1; i <= n; i ++)
22         dist[i] = (i == source ? 0 : INF);
23     for(int k = 1; k < n; k ++) {
24         flag = false;
25         for(int i = 1; i <= n; i ++) {
26             for(int j = 0; j < G[i].size(); j ++) {
27                 edge e = G[i][j];
28                 if(dist[e.to] > dist[i] + e.cost) {
29                     dist[e.to] = dist[i] + e.cost;
30                     flag = true;
31                 }
32             }
33         }
34         if(!flag) break;
35     }
36     return dist[n];
37 }
38 
39 int main() {
40     cin >> t >> n;
41     int a, b, w;
42     for(int i = 0; i < t; i ++) {
43         cin >> a >> b >> w;
44         addedge(a, b, w);
45         addedge(b, a, w);
46     }
47     cout << Bellman_Ford(1) << endl;
48     return 0;
49 }
50 // */

View Code

　　　　SPFA：这是Bellman-Ford算法的一种队列优化算法，具体是怎么个优化法呢，听我下面详细道来......

　　SPFA算法全称为Shortest Path Fast Algorithm，在1994年由西南交通大学段凡丁提出，与Bellman-Ford算法一样，用于求解含负权的最短路问题以及判断是否存在负权环。在不含负权环的题情况下优先选择堆优化的Dijkstra算法求最短路径，这就避免SPFA出现最坏的情况。SPFA算法的基本思路与Bellman-Ford算法相同，即每个节点都被用作用于松弛其相邻节点的备选节点。相较于Bellman-Ford算法，SPFA算法的提升在于它并不盲目尝试所有节点，而是维护一个备选节点队列，并且仅有节点被松弛后才会放入队列中。整个流程不断重复直至没有节点可以被松弛。

　　下面给出这个算法的代码吧：

 1 #include <iostream>
 2 #include <queue>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 struct edge {
 7     int to, cost;
 8 };
 9 const int maxn = 1000 + 5, INF = 0x3f3f3f3f;
10 vector <edge> G[maxn];
11 int t, n, now, dist[maxn];
12 bool vis[maxn];
13 
14 void addedge(int u, int v, int w) {
15     G[u].push_back({v, w});
16 }
17 
18 int Spfa(int source) {
19     memset(vis, false, sizeof vis);
20     for(int i = 1; i <= n; i ++)
21         dist[i] = (i == source ? 0 : INF);
22     queue <int> Q;
23     Q.push(source);
24     vis[source] = true;
25     while(!Q.empty()) {
26         now = Q.front();
27         Q.pop();
28         for(int i = 0; i < G[now].size(); i ++) {
29             edge e = G[now][i];
30             if(dist[e.to] > dist[now] + e.cost) {
31                 dist[e.to] = dist[now] + e.cost;
32                 if(!vis[e.to]) Q.push(e.to);
33             }
34         }
35     }
36     return dist[n];
37 }
38 
39 int main() {
40     cin >> t >> n;
41     int a, b, w;
42     for(int i = 0; i < t; i ++) {
43         cin >> a >> b >> w;
44         addedge(a, b, w);
45         addedge(b, a, w);
46     }
47     cout << Spfa(1) << endl;
48     return 0;
49 }

View Code

　　　　Floyd-Warshall：这个算法的本事很大，可以用来求所有结点的最短路，但用此算法求单源最短路也是可以的，就显得比较大材小用，本领强其复杂度必然臃肿......好了下面我介绍一下该算法的基本思路吧。

　　Floyd-Warshall算法通过逐步改进两个顶点之间的最短路径来实现，直到估计是最优的。

是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权（但不可存在负权回路）的最短路径问题，同时也被用于计算有向图的传递闭包^[2]。

Floyd-Warshall算法的时间复杂度为O(N3) $，空间复杂度为O(N2) 。$

　　原理：Floyd-Warshall算法的原理是动态规划。

设D(i, j, k) $为从i 到j 的只以(1....k) 集合中的节点为中间节点的最短路径的长度。$

若最短路径经过点k， $D(i, j, k) = D(i, k, k - 1) + D(k, j, k - 1)；$
若最短路径不经过点k，则 $D(i, j, k) = D(i, j, k - 1)。$

因此， $D(i, j, k) = min(, D(i, j, k - 1), D(i, k, k - 1) + D(k, j, k - 1))；。$

在实际算法中，为了节约空间，可以直接在原来空间上进行迭代，这样空间可降至二维。

　　参考代码：

 1 // /*Floyd-Warshall算法：TLE,具体时间不详
 2 #include <iostream>
 3 #include <queue>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 struct edge {
 8     int to, cost;
 9 };
10 const int maxn = 1000 + 5, INF = 0x3f3f3f3f;
11 int t, n, now, dist[maxn][maxn];
12 
13 int Floyd_Warshall(int source, int End) {
14     for(int k = 1; k <= n; k ++) {
15         for(int i = 1; i <= n; i ++) {
16             for(int j = 1; j <= n; j ++) {
17                 if(dist[i][j] > dist[i][k] + dist[k][j])
18                     dist[i][j] = dist[i][k] + dist[k][j];
19             }
20         }
21     }
22     return dist[source][End];
23 }
24 
25 int main() {
26     cin >> t >> n;
27     int a, b, w;
28     for(int i = 1; i <= n; i ++) {
29         for(int j = 1; j <= n; j ++) {
30             if(i == j) dist[i][j] == 0;
31             else dist[i][j] = INF;
32         }
33     }
34     for(int i = 0; i < t; i ++) {
35         cin >> a >> b >> w;
36         dist[a][b] = min(dist[a][b], w);
37         dist[b][a] = min(dist[b][a], w);
38     }
39     cout << Floyd_Warshall(1, n) << endl;
40     return 0;
41 }
42 // */

View Code

　　这个题目就到此结束吧......