最短路算法及其延伸

个人算法训练题集： http://acm.hust.edu.cn/vjudge/contest/toListContest.action#contestType=0&contestRunningStatus=0&contestOpenness=0&title=风斩冰华&manager=

密码xwd，欢迎大家一起来学习。

首先复习一下最短路问题，即求某两点之间边权最小的一条路径。这样就延伸出了两个子问题：

求任意两点的距离，还是求图上固定一个起点到某点的距离？

验题：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=85798#problem/A

任意两点的距离

求任意两点的距离可以用floyd算法，类似于Warshell算法求传递闭包，我认为是在图上加了一条虚边，使得这条虚边是最短路径而已。floyd算法的基本思想是贪心（DP貌似也说得过去），给出（状态转移方程?）G[i][j] = max(G[i][j], G[i][k]+G[k][j]) 以及代码：

1     #include <algorithm>  2     #include <iostream>  3     #include <iomanip>  4     #include <cstring>  5     #include <climits>  6     #include <cstdlib>  7     #include <complex>  8     #include <fstream>  9     #include <cassert> 10     #include <cstdio> 11     #include <bitset> 12     #include <vector> 13     #include <deque> 14     #include <queue> 15     #include <stack> 16     #include <ctime> 17     #include <set> 18     #include <map> 19     #include <cmath> 20  21     using namespace std; 22  23     const int maxn = 222; 24     const int INF = 0xffffff; 25     int G[maxn][maxn]; 26     bool vis[maxn][maxn]; 27     int n, m; 28     int u, v, w; 29  30     void init() { 31         memset(vis, 0, sizeof(vis)); 32         for(int i = 0; i < maxn; i++) { 33             for(int j = 0; j < maxn; j++) { 34                 if(i == j) { 35                     G[i][j] = 0; 36                 } 37                 else { 38                     G[i][j] = INF; 39                 } 40             } 41         } 42     } 43  44     int main() { 45         // freopen("in", "r", stdin); 46         while(~scanf("%d %d", &n, &m) && n + m) { 47             init(); 48             for(int i = 0; i < m; i++) { 49                 scanf("%d %d %d", &u, &v, &w); 50                 // G[u][v] = min(G[u][v], w); 51                 // G[v][u] = min(G[v][u], w); 52                 if(G[u][v] > w) { 53                     G[u][v] = G[v][u] = w; 54                 } 55             } 56             for(int k = 1; k <= n; k++) { 57                 for(int i = 1; i <= n; i++) { 58                     for(int j = 1; j <= n; j++) { 59                         if(G[i][k] + G[k][j] < G[i][j]) { 60                             G[i][j] = G[i][k] + G[k][j]; 61                         } 62                     } 63                 } 64             } 65             printf("%d/n", G[1][n]); 66         } 67     }  floyd

图上固定一个起点到某点的距离

首先复习一下dijkstra，dijkstra的思路是设置一个集合S，集合S表示目前已知的所有点。再往这个集合里面加点，加的这个点一定是距离这个集合最近的那个点。然后加入之后再去更新目前起点到加入的各点之间的最短距离。注意此时更新d数组的点i还未被加入到集合S内。待下一次更新集合S的元素的时候才会被更新进集合内，并继续寻找起点到下一个相邻点的最短路径。代码如下：

1 #include <algorithm>  2 #include <iostream>  3 #include <iomanip>  4 #include <cstring>  5 #include <climits>  6 #include <complex>  7 #include <fstream>  8 #include <cassert>  9 #include <cstdio> 10 #include <bitset> 11 #include <vector> 12 #include <deque> 13 #include <queue> 14 #include <stack> 15 #include <ctime> 16 #include <set> 17 #include <map> 18 #include <cmath> 19  20 using namespace std; 21  22 const int maxn = 105; 23 const int inf = 0xffffff; 24 int d[maxn]; 25 int G[maxn][maxn]; 26 int vis[maxn]; 27 int n, m; 28  29 void init() { 30     memset(vis, 0, sizeof(vis)); 31     for(int i = 0; i <= n; i++) { 32         d[i] = inf; 33         for(int j = 0; j <= n; j++) { 34             G[i][j] = G[j][i] = inf; 35         } 36         G[i][i] = 0; 37     } 38 } 39  40 void dijkstra(int start) { 41     d[start] = 0; 42     for(int i = 1; i <= n; i++) { 43         int u = -1; 44         for(int j = 1; j <= n; j++) { 45             if(!vis[j]) { 46                 if(u == -1 || d[j] < d[u]) { 47                     u = j; 48                 } 49             } 50         } 51         vis[u] = 1; 52         for(int j = 1; j <= n; j++) { 53             if(!vis[j]) { 54                 d[j] = min(d[u]+G[u][j], d[j]); 55             } 56         } 57     } 58 } 59  60 int main() { 61     // freopen("in", "r", stdin); 62     int u, v, w; 63     while(~scanf("%d %d", &n, &m) && n + m) { 64         init(); 65         while(m--) { 66             scanf("%d %d %d", &u, &v, &w); 67             G[u][v] = G[v][u] = w; 68         } 69         dijkstra(1); 70         printf("%d/n", d[n]); 71     } 72 }  朴素dijkstra

还可以使用小根堆对此算法进行优化，用邻接表存储各点以及边权的信息。思路是一样的，用一个集合来维护已知的所有点。小根堆维护两个数据：一个是某边的权值w，另一个是某边的未扫描顶点v。pop时送出当前最短距离wm和顶点vm（因为放入堆内的下一个点v都是可达的，所以贪心地选取边权最小的下一个点来进行计算）。之后就是遍历当前点vm的所有邻接的边了。

1 #include <algorithm>  2 #include <iostream>  3 #include <iomanip>  4 #include <cstring>  5 #include <climits>  6 #include <complex>  7 #include <fstream>  8 #include <cassert>  9 #include <cstdio> 10 #include <bitset> 11 #include <vector> 12 #include <deque> 13 #include <queue> 14 #include <stack> 15 #include <ctime> 16 #include <set> 17 #include <map> 18 #include <cmath> 19  20 using namespace std; 21  22 typedef struct E { 23     int w; 24     int v; 25     E() {} 26     E(int vv, int ww) : v(vv), w(ww) {} 27 }E; 28  29 typedef pair<int, int> PII; 30 const int inf = 0x7f7f7f7f; 31 const int maxn = 1111; 32  33 priority_queue<PII, vector<PII>, greater<PII> > pq; 34 vector<E> e[maxn]; 35 int d[maxn]; 36 int n, m, u, v, w; 37  38 void dijkstra(int s) { 39     for(int i = 0; i <= n; i++) d[i] = inf; 40     while(!pq.empty()) pq.pop(); 41     d[s] = 0; 42     pq.push(PII(0, s)); 43     while(!pq.empty()) { 44         PII cur = pq.top(); pq.pop(); 45         w = cur.first; 46         v = cur.second; 47         if(d[v] < w) continue; 48         for(int i = 0; i < e[v].size(); i++) { 49             if(d[e[v][i].v] > d[v] + e[v][i].w) { 50                 d[e[v][i].v] = d[v] + e[v][i].w; 51                 pq.push(PII(d[e[v][i].v], e[v][i].v)); 52             } 53         } 54     } 55 } 56  57 int main() { 58     // freopen("in", "r", stdin); 59     while(~scanf("%d %d", &n, &m)) { 60         for(int i = 0; i < m; i++) { 61             scanf("%d %d %d", &u, &v, &w); 62             e[u].push_back(E(v, w)); 63             e[v].push_back(E(u, w)); 64         } 65         dijkstra(1); 66         for(int i = 1; i <= n; i++) printf("%d ", d[i]); 67             printf("/n"); 68         printf("%d/n", d[n]); 69     } 70 }  小根堆优化dijkstra

有了最短路算法，接下来可以分析一下dijkstra算法，进而得出求次短路的算法。

验题：http://poj.org/problem?id=3255

次短路问题

dijkstra算法的思想不再赘述，下面我们考虑次短路与最短路的关系。

次短路的获得有两种方法，一是起点到某个顶点的最短路再额外加上一条边，二是到某个顶点的次短路再额外加上一条边。因此我们要求的是起点到所有顶点的最短路和次短路。额外将一条次短的边放入小顶堆内，之前从小顶堆内往外提取的只是需要距离集合最短的一条边所连接的一个顶点，现在需要额外记下通往下一个顶点的权值。

1 #include <algorithm>  2 #include <iostream>  3 #include <iomanip>  4 #include <cstring>  5 #include <climits>  6 #include <complex>  7 #include <fstream>  8 #include <cassert>  9 #include <cstdio> 10 #include <bitset> 11 #include <vector> 12 #include <deque> 13 #include <queue> 14 #include <stack> 15 #include <ctime> 16 #include <set> 17 #include <map> 18 #include <cmath> 19  20 using namespace std; 21  22  23 typedef struct E { 24     int w; 25     int v; 26     E() {} 27     E(int vv, int ww) : v(vv), w(ww) {} 28 }E; 29  30 typedef pair<int, int> PII; 31 const int maxn = 5555; 32 const int inf = 0xffffff; 33  34 priority_queue<PII, vector<PII>, greater<PII> > pq; 35 vector<E> e[maxn]; 36 int d1[maxn], d2[maxn]; 37 int n, m, u, v, w; 38  39 void dijkstra(int s) { 40     for(int i = 0; i <= n; i++) d1[i] = d2[i] = inf; 41     while(!pq.empty()) pq.pop(); 42     d1[s] = 0; 43     pq.push(PII(0, s)); 44     while(!pq.empty()) { 45         PII cur = pq.top(); pq.pop(); 46         w = cur.first; 47         v = cur.second; 48         if(d2[v] < w) continue; 49         for(int i = 0; i < e[v].size(); i++) { 50             int dd = w + e[v][i].w; 51             if(d1[e[v][i].v] > dd) { 52                 swap(d1[e[v][i].v], dd); 53                 pq.push(PII(d1[e[v][i].v], e[v][i].v)); 54             } 55             if(d2[e[v][i].v] > dd && dd > d1[e[v][i].v]) { 56                 d2[e[v][i].v] = dd; 57                 pq.push(PII(d2[e[v][i].v], e[v][i].v)); 58             } 59         } 60     } 61 } 62  63 int main() { 64     // freopen("in", "r", stdin); 65     while(~scanf("%d %d", &n, &m)) { 66         for(int i = 0; i < m; i++) { 67             scanf("%d %d %d", &u, &v, &w); 68             e[u].push_back(E(v, w)); 69             e[v].push_back(E(u, w)); 70         } 71         dijkstra(1); 72         printf("%d/n", d2[n]); 73     } 74 }  小根堆优化dijkstra次短路

【转载请声明作者及出处，谢谢】