[关闭]
@lunar 2016-07-06T14:25:01.000000Z 字数 4001 阅读 1407

HiHo一下 最短路径问题 Week23Week24Week25

HiHo

描述

这两周的题目都是要求最短路径，不同的是Week23和Week25是单源最短，Week24是每两个点最短。
因为两周合并起来所以输入输出就不贴出来了，可以通过标题链接过去。

思路

第22周 Dijkstra

这里要求的是单源最短路径，也就是说给定一张图，要求出对于特定的源点i，其他所有点到i的最短距离。
现在已知的最快的算法是Dijkstra's算法，本质上是个广度优先算法，最终会得到一棵最短路径树。
维基百科的描述是这样的：

这个算法是通过为每个顶点 v 保留目前为止所找到的从s到v的最短路径来工作的。初始时，原点 s 的路径长度值被赋为 0 （d[s] = 0），若存在能直接到达的边（s,m），则把d[m]设为w（s,m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大，即表示我们不知道任何通向这些顶点的路径（对于 V 中所有顶点 v 除 s 和上述 m 外 d[v] = ∞）。当算法结束时，d[v] 中存储的便是从 s 到 v 的最短路径，或者如果路径不存在的话是无穷大。 Dijkstra 算法的基础操作是边的拓展：如果存在一条从 u 到 v 的边，那么从 s 到 v 的最短路径可以通过将边（u, v）添加到尾部来拓展一条从 s 到 v 的路径。这条路径的长度是 d[u] + w(u, v)。如果这个值比目前已知的 d[v] 的值要小，我们可以用新值来替代当前 d[v] 中的值。拓展边的操作一直运行到所有的 d[v] 都代表从 s 到 v 最短路径的花费。这个算法经过组织因而当 d[u] 达到它最终的值的时候每条边（u, v）都只被拓展一次。

算法维护两个顶点集 S 和 Q。集合 S 保留了我们已知的所有 d[v] 的值已经是最短路径的值顶点，而集合 Q 则保留其他所有顶点。集合S初始状态为空，而后每一步都有一个顶点从 Q 移动到 S。这个被选择的顶点是 Q 中拥有最小的 d[u] 值的顶点。当一个顶点 u 从 Q 中转移到了 S 中，算法对每条外接边 (u, v) 进行拓展。

通过一张图可以简明地看出其工作原理
Dijkstra's Algorithm
不加任何优化的算法复杂度为表示点的个数。如果加了优先队列，比如斐波那契堆实现的优先队列，那么复杂度为表示边数。但是需要注意的是，该算法无法解决有负边的情况。
另外这道题要求的是s到t的距离，而不需要s到所有顶点，所以当优先队列弹出t的时候就可以结束算法输出了。

第23周 Floyd

这周是要求出任意两个点之间的最短距离，当然，你可以对每个点都使用一次Dijkstra算法，但是相比之下，Floyd算法更加简单。该算法的原理可以用数学归纳法来证明。
如果说，从x到y的距离比从x到k，再从k到y的距离大，那么我们就可以用k的信息来更新（x,y）的距离，这里我们称k为中间点。
一开始我们加上所有路径没有中间点的限制，那么所有路径就只能直通。
然后我们加上可以通过中间点1，那么就可以用1号点来更新信息。
逐步放开限制，可以通过中间点2~n，最后我们就会得到一个没有限制的最小路径，也就是要求的最小路径。
该算法的复杂度为,可以处理负边问题。

第25周 SPFA

这个算法是Shortest Path Faster Algorithm的缩写，从字面上看就是速度较快的算法。这个算法其实是ballman-ford算法的一种优化，其本身还有LLL和SLF两种优化，但是由于算法的效率不是很稳定，所以在实际应用中并不常见，而且由于算法的发明者西南交大的段丁凡对该算法的证明不严谨，所以也没有得到主流学术界的认可。所以该算法虽然平均速度快，但最坏情况的效率非常慢，而且只在稀疏图下表现较好()
闲话少提，我们来看一下这个算法的步骤。
我们要用到队列这种先进先出的数据结构，利用邻接表来表示树。
1.初始化数据，dis[x]表示x到源点距离，初始化为无穷大，flag[x]表示x是否在队列里,初始化为false，源点s入队。
2.弹出队首top，利用队首信息来更新dis，对于队首能到达的每个节点i，如果那就用后者更新它，并将i入队（如果dis[i]没有更新就不要傻乎乎的入队了）。
3.重复步骤2直到队列为空。
4.输出dis[t]，即源点到目标的距离。

代码

Dijkstra代码

  1. #include<iostream> 
  2. using namespace std;
  3. #define infinity 10000000
  4. #define make_pair(y,w) pair<int,int>(y,w)
  5. #include<vector>
  6. #include<queue>
  8. std::priority_queue <pair<int,int> > nP;    // Using priority queue to provide the nearest point
  10. int main(){
  11.     int n,m,s,d,x,y,w,i,ty,tw;
  12.     cin >>n >>m >> s >>d;
  13.     std::vector<vector<pair<int,int> > > tree(n+1); 
  14.     while(m--){
  15.         cin >> x >> y >> w;
  16.         tree[x].push_back(pair<int,int>(y,w));
  17.         tree[y].push_back(pair<int,int>(x,w));
  18.     }
  19.     std::vector<int> flag(n+1,false);   // denote which set this node belongs to
  20.     std::vector<int> dis(n+1,infinity); // represent the distance node s and certain node
  21.     dis[s] = 0;
  22.     for(nP.push(make_pair(0,s));!nP.empty();){
  23.         int t = nP.top().second;
  24.         nP.pop();
  25.         if(flag[t]) continue;
  26.         flag[t] = true;
  27.         if(t == d) break;
  28.         //Core part 
  29.         for(i=0;i<tree[t].size();i++){
  30.             ty = tree[t][i].first;
  31.             tw = tree[t][i].second;
  32.             if(dis[ty]>dis[t]+tw){
  33.                 dis[ty] = dis[t] + tw;
  34.                 nP.push(make_pair(-dis[ty],ty));
  35.             }
  36.         }
  37.     }
  38.     cout << dis[d];
  39.     return 0;
  40. }

Floyd代码

  1. #include<iostream>
  2. #include<algorithm>
  3. using namespace std;
  4. #define MAX 105
  5. #define infinity 1000000
  6. int map[MAX][MAX];
  7. bool isSame(int x, int y, int z){
  8.     if((x!=y)&&(y!=z)&&(x!=z)) return false;
  9.         else return true;
  10. }
  11. int main(){
  12.     int n,m,x,y,v;
  13.     cin >> n >>m;
  14.     for(int i=0;i<=n;i++)
  15.         for(int j=0;j<=n;j++){
  16.             if(i==j) map[i][j] = 0;
  17.             else map[i][j] = infinity;
  18.         }
  19.         while(m--){
  20.             cin >>x>>y>>v;
  21.              if(map[x][y] > v){
  22.              map[x][y] = v;
  23.              map[y][x] = v;
  24.             }
  25.         }
  26.         for(int k=1;k<=n;k++){
  27.             for(int i=1;i<=n;i++)
  28.                 for(int j=1;j<=n;j++){
  29.                     if(!isSame(i,j,k))
  30.                         map[i][j] = min(map[i][j],map[i][k]+map[k][j]);
  31.                 }
  32.         }
  33.         for(int i=1;i<=n;i++){
  34.             for(int j=1;j<=n;j++) cout <<map[i][j] << " ";
  35.             cout <<endl;
  36.         }
  37.     return 0;
  38. }

SPFA代码

  1. #include<iostream>
  2. #include<queue>
  3. #include<vector>
  4. using namespace std;
  5. #define infinity 10000000
  7. int main(){
  8.     int n,m,s,t,x,y,v;
  9.     n = infinity;
  10.     cin >> n >>m >> s >>t;
  11.     std::vector<vector<pair<int,int> > > tree(n+1);
  12.     std::vector<int> dis(n+1,infinity);
  13.     std::vector<int> flag(n+1,true);
  14.     std::queue<int> que;
  15.     while(m--){
  16.         cin >> x >> y >> v;
  17.         tree[x].push_back(pair<int,int>(y,v));
  18.         tree[y].push_back(pair<int,int>(x,v));
  19.     } 
  20.     dis[s] = 0;
  21.     que.push(s);
  22.     flag[s] = false;
  23.     while(!que.empty()){
  24.         int top = que.front();
  25.         que.pop();
  26.         for(int i=0;i<tree[top].size();i++){
  27.             int temp = tree[top][i].first;
  28.             if(dis[temp]>(dis[top]+tree[top][i].second)){
  29.                 dis[temp]=(dis[top]+tree[top][i].second);
  30.                 if(flag[temp]){
  31.                     que.push(temp);
  32.                     flag[temp] = false;
  33.                 }
  34.             }           
  35.         }
  36.         flag[top] = true;
  37.     }
  38.     cout<< dis[t];
  39.     return 0;
  40. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注